How do you pay an artist? Generously. As much as you can afford, and maybe take out a line of credit or something?

Okay, so, I still stand by that, but, the deal is you'll get better results if you take someone on in such a way that it becomes a shared project, rather than you hiring them as an outside contractor. Just, make sure that you have some sort of mutually accepted written agreement about how money will be divided up should there be any. Also, you'll need to be open to their suggestions on gameplay and design, because it's their baby too now.
If you just want to hire a freelance artist, then decide what your art budget is, and what you want it to buy ahead of time. Then, if you're making a post in a classified section of an artist community or something, include that information. This may seem like common sense, but way too many people are really vague when trying to hire an artist.
Always pay after the work is completed. And don't try to use "royalties" as an extra carrot. Set your offer ahead of time and let the artist take it or leave it. If nobody's taking it, then you're not offering enough.
And when you find an artist who wants to work on your project, and has a style you like, keep in touch and be nice to them, because general courtesy and respect will do more for an artist's work ethic than money ever will.
So, yeah, that's my two bits as an artist who does some freelance...