Its a really tough question. I have tried many of the routes suggested above. Elance, 99design and carbonmade. None of the experiences were great - elance and 99design work well for one off projects such as logo design and both vehicles provide many cost effective solutions, but designers are often in other countries in different time-zones and may speak different languages and the result is often poor communication, difficulty setting/meeting deadlines and lack of real understanding and buy-in from the designer.

Carbonmade is higher end and really just provides portfolios of design work to peruse and contact information - I found the hit rate on making contact to be very low and ultimately ran into communication/timing/buy-in problems here too.

Short of engaging a design cofounder/partner/employee, your best bet is to use a site like carbonmade to try to find someone local and to meet face to face and establish a relationship with the designer - difficult unless you are in NYC or LA/SF or other design hubs.

I echo the sentiment that design is critical.

Good luck.