Here is a good blog post I read some time ago about how this company chose their designer:

http://www.barenakedapp.com/the-team/how-we-picked-the-designer

Figuring out the best designer for your site is, generally, more art than science. Just like choosing a developer. One thing you can do to reduce your risk is to hire someone for a small task first (say, do the logo), and if you like their work, ask them to do the whole project.