I’m no designer, so I’ve had to hire designers to make icons for my iPhone apps a few times. I actually just got one made for Stunning. Here’s what I normally do:

1. Search Dribbble for designers who have done good work, in the style that I want. Sometimes I can even find a designer who has done something really close to what I want. I generally get a really good deal then, because they already know how to do what I want, and they're just modifying a process that they already know. Dribbble even shows you who is available for work, and you can message designers right from within Dribbble. Price-wise, over the years I've paid between $3000 and $300 for design work, depending on complexity.
2. Write a descriptive email/Dribbble message that describes what I want in as much detail as possible, and ask for a quote.
3. Make sure that I get quotes from multiple designers, so that I can compare the market and play the quotes against each other when negotiating.
4. Once I've collected a few quotes, sometimes I ask the person with the highest price (if they're my #1 choice) to bring their price down by some amount, mentioning other, lower quotes that I've gotten (for leverage). Note that they might not go for it, so you have to be prepared to walk away completely and get another designer to work on the icon.
5. Pick a designer, and pay them some up-front money to get them started. In most cases, I've paid 40% or 50% up front, and the rest on completion. I've never had a problem with getting revisions made to my icons, but I keep the number of revisions within reason. It's very good to start with a well-defined idea so you need less revisions later. Designers are usually happy to do them, though, because they want you to have a good product in the end. Oh, and one more thing, when describing the revisions that you want, you might want to use something like LittleSnapper or Skitch to annotate and draw arrows on your image, to accurately point out where you want things moved to/from.

Then, the designer will normally tell you how long it'll take for them to show you something, and they'll send you some sketches so you can agree on a direction if need be, or they'll just get started on the icon and show you something more final if everything is more well-defined.

If you do this a few times, you’ll end up with designers that you trust, and who you work well with. It’s a good idea to start with those guys first and see what they can do for you. They’ll appreciate it, and you’ll have more of an idea what to expect because you’ve been through the process with them before.

Hope this helps! It’s not a difficult process (if you know what you want your icon to be). Deciding on the icon is always the most difficult part for me.