What type of art do you want? Realistic, semi-realistic, anime, 8-bit, highly stylized, some kind of mix? If you are not sure, then head over to any website where artists show off their work and look until you find something you like.

Decide if you want to have any concept art. If you can afford it, it will be worth it. You can do general concept art: to establish the overall feeling for the game (the atmosphere), or more specific concept art: characters, places, events, etc... I did not do concept art for my game, but that meant that I had to find artists who could do a good job of designing the places and characters.

Think about your budget. How much can you spend on art? How will it be divided between different art asset types? You might not have a good answer for this yet, especially if you don't know how much artists normally charge for the kind of work you want them to do. That's fine, you can figure it out later. Understanding your budget will help you with picking the right artists, and force you to cut down on content, which is almost always a good thing.

Decide where you'll get your inspiration from. I ended up writing dialog to fit the portraits that were drawn for the characters. I couldn't help but do that once I saw the characters' actual faces. This is not a bad thing, but if you have a very good idea of what a character is supposed to be, then make sure the art will conform to that, rather than you conforming to the art.

Prepare to spend some time finding the right artist. Depending on your needs this can take anywhere from two weeks to two months. Be ready, and make sure you have something to do during that time.

Find a website where you can find the kind of artists you are looking for. I needed a 2D background artist, and a character artist and animator. DeviantArt is probably the best place for that.

Go to the website and make a post.* Make sure to post it in the right place. Some are for people who are offering payment, and others are for people who are just looking for a collaborator. In your post, outline everything you want the artist to do. Don't assume things. Here are some things in particular that you should mention:

Are you not offering enough payment for this job? This is probably true if you got a lot of replies from amateur artists.

Perhaps some expectations you've listed are too demanding.

It's possible there are only a few people who can do what you want. Either the art style is too specific, or – if, let's say, you are looking for an animator – there aren't a lot of animators looking at the forums where you posted.

First, look at their portfolio. It should either demonstrate that they can do the kind of art you want them to do, or, at least, show that they are capable enough to do it. If after looking at their art, you don't feel like they make a good candidate, simply tell them "no, thank you", and let them know why you rejected them. This is a small courtesy that will allow them to grow in the right direction, if they want to do the kind of work you are offering.

You can look at their resume and/or previous experience if they have it, though, I personally didn't care one bit. If they can do the kind of art I want, then they are good enough for me.

If you haven't set the price, look at how much they are asking. This will help you get a good perspective on what's normal for the kind of work you are offering. Realize that the variance in price can be pretty high, since its based on many factors: artist's experience, location, and interest in the project.

Email them back with any questions you have. If you have none, just ask them if they've read your post carefully and understand all of it. Do they have any questions? You'll be surprised how many people (>40%) will never get back to you on this. This is an easy way to not waste your time on people who are not really interested or can't commit to your project.

I believe in “the one” feeling when it comes to finding the right artist. This is especially important if your art is specific or unique. You want to find an artist who make you go, “Wow, that's what I was looking for and more!” It's like falling in love.

Can you afford to ask each artist to create a sample and pay them for it? If yes, then do it: you'll get much better artists applying, since they can see you are being very professional upfront.

If no, then ask them to do it for free. (There is a third middle option, see below.) Ideally, you've mentioned this in your post. Don't present this as a surprise. To minimize the amount of free work they'll have to do, split the task into several steps for them.

Send them the description/concept art to do. This should be the most complicated/difficult one. One that will let the good artists shine through. However, it should also by typical for your game. (Don't ask an artist to draw a town, if most images they'll actually draw are of a cave.)

Ask the artist to draw a sketch based on the given description/concept art. It should include enough interesting detail so you can see what they have in mind. (A cube as a substitute for a house won't do.)

Once you have the sketch, if it's not good enough, politely reject them (and tell them why). (The third method of paying for samples is to pay them right here, but only if the sketch is good enough.) If it's good, ask them to paint some (or if you are paying them for the sample, then all) parts of the picture to show you what it will look like when it done. What I did is just draw several rectangles for them to paint inside. They should paint it as it would look in the final revision.

If the final result is good enough, then this artist becomes a candidate. Make sure to let them know ahead of time, that just because they make it through the test, doesn't mean they are automatically hired. You'll still have to pick the best out of all the candidates you have. I think you'll often find that there is that one artist that just sends shivers down your spine when you see how perfectly they've implemented your vision.

This whole process gives a chance for good artists to show that they are talented, dedicated, and interested. Often, they'll go above and beyond what you've expected. This process also gives you a chance to look at the artist's communication style, their understanding of what you are trying to accomplish, their reaction to suggestions and criticism, etc...

Pretty much everything you've included in your original forum post (or message).

A clear schedule. At the very least mention how many assets per week you expect to receive.

How will you handle a scenario where one party wants to make a change to the contract?

How will you handle a scenario where one party wants to quit? (Realize that something might come up in your own life, where you no longer want to work on your game.)

Consider other scenarios. What happens if you want to go over the maximum number of revisions for an art asset? What happens if the art quality starts to decline? What happens if the artist is lagging behind schedule? What happens if you want to them to do more/less work? Different work?

Under what conditions can a party terminate the contract?

Number of revisions left for each art asset.

Have a document to keep track of assets that need to be done, assets that are being worked on (I count an asset as being worked on as soon as I tell the artist I need it), assets that are done, and assets that are done and partially/fully paid for.

When an artist sends you the first draft, plug it into your game immediately. Don't look at it on its own. This will might reveal many things that need to be corrected, that you would have otherwise missed. (I've made the mistake of not doing this, and then once one of the backgrounds was done, I've realized it was completely not to scale.) Mistakes like this can be very costly to fix. If a mistake does occur, it's your fault, and not the artist's.

When checking if an art asset is right, make sure to look over all the specifications you gave. You might not even remember all of them, so go check that email you wrote. Make sure all your comments/corrections have been implemented. Make sure the asset fits into the game well.

Have the easiest possible pipeline from the artist to the game. Ideally, you have a repository that everyone uses. Basically, count all the steps you have to take to see a new art asset in the actual game, and see if you can simplify this process. (For example, I had to manually change the Texture Importer settings in Unity3D for every single texture I wanted to add to the project. This quickly became a very huge time sink, so I found a script that does this automatically, modified it to my liking, and saved myself hours of work.)

Check your budget to make sure you are still on track. I've been checking my budget each month (and more frequently in the beginning) to make sure I am not going to spend more than I have.