How to find a competent knife sharpener
Allow me to help you fast forward through my years of pain trying to get my knives sharpened.  I looked all over to find a local sharpening service.  I called fancy restaurants, chain restaurants, and restaurant supply stores.  I found one who said they performed the service and promptly had three knives really scratched up.

I tried doing the sharpening myself.  This isn't a bad idea, but most home sharpening systems won't let you put a true new edge on your knife.  The best luck I had was with a Spyderco Sharpmaker.  This will do a good job, but I found it to be a pain, and it never really got me the results I was looking for.  

Then I discovered sharpening by mail.  Its awesome.  Ship your knives off, get them back in a state where you should keep bandaids handy.  Here is an article from the Wall Street Journal comparing several services.  I used the Knife Guy and couldn't have been happier.  Unfortunately, it looks like he's no longer accepting new customers since the article came out, but the other services they compared seem to have done well.

One other Note.  I read in an interview with Alton Brown that he only sends his knives off to be professionally sharpened once a year or so.  If you use a honing steel properly that's all you should need.  I've certainly found that to be the case with me.