Twice I've just gone to sites like elance, Guru, and ODesk to find a graphic designer, and both times found someone adequate (and relatively cheap). Once it was a pretty good recent graduate who was just starting out. (And with a few iterations with good feedback, we got the artwork where we wanted it.)
Besides asking for samples (and/or references), I don't know what else you can do. A small business owner once advised me to start any contractor (or several contractors) on a small project, just to see if I liked their work and their interpersonal skills -- and then give more work based on that initial experience.