99 Designs is a popular choice, along with some similar services like Crowd Spring and Design Crowd.
You can also find a designer to work directly with you, which offers more control over the process but can be more expensive and time consuming.
Creating a logo yourself (if you're not a designer) can be problematic. A lot of people try doing this thinking it will be easy, but then run into problems -- the same reason why designers who think they can tackle writing code over a weekend end up with non-scalable solutions.
A good logo needs to stand on its own, as well as look good as a part of an overall design.
It should look good in black and white, as well as color. (I'd also recommend it be done using flat colors -- shadows and gradients look great on screen, but don't translate well when they are printed.)
It should be legible when it is small (1cm x 1cm) as well as large (and it should be designed in a vector format, to allow for re-sizing at any size needed).
It should be able to be printed on a t-shirt/baseball-cap/apparel, a business card, stationary/invoices, or a billboard -- and look good on all of them.
The professional designers that I know don't like sites like 99designs -- see http://www.no-spec.com/faq/ for multiple reasons against logo contests. The main reason why I've avoided them is that I've seen entries that have had elements that were "borrowed" from iStockPhoto (or other assets found on the web) -- which could invalidate any trademark or copyright protection.
It's also very embarrassing to be featured on sites like: http://youthoughtwewouldntnotice.com/blog3/
We had used www.thelogoloft.com, which seemed very reputable, and we didn't have a problem in the creation of our logo. Now though, they seem to have went bankrupt so I can't get a few files (business card template), which I had lost local copies of. I was one of the lucky ones who finished our project before they went out of business. In trying to figure out why they weren't answering phone calls and support request it seems a lot of people got burned, having paid upfront for big packages.
Anyway, the important part is that the former CEO/Founder re-opened under another name. I had found it awhile back but can't seem to anymore. If you do go with an online service beware the name Aaron Carr of Montgomery, Al.
If I can find the name of his new company I'll edit this post.
Try to design your own. It's what a lot of start ups end up doing here in India. Try Corel Draw and make it simple. It's easy enough.
A quick, free method is to make a typographic logo. This is a great way to do branding while your startup is in the very early stages. The simplest method is to type out the name and then try applying various fonts and text decorations.