Like the post above mentions, the demos are definately worth listening to. Newer engineers trying to come up may think their work is good, but really don't know what they are doing yet, or just suck in general. Listening to a demo will at least help weed a few people out. Also, you can hear what the enginee does with specific genres. He/she may be able to mix a great hip-hop cd, but has no idea where to begin on a metal album. This can also help narrow your search.
Word of mouth is huge in this business. Try to get in contact with artists who have worked with the engineer previously. If they had a bad experience, it's quite possible you will as well. Also they will have insight on how the engineers worked. They may be great at what they do, but be hard to work with.
Personally, I would first decide what the an appropriate value would be. If its just your first recording, and its a little weak, there is no need spending a few hundred dollars on something that isn't worth it. They can make it sound better, but if it sucks, they'll just be polishing something that sucks to begin with. On the other side, if this is something that you've spent a lot of hours and money on already, then you don't want to go to someone that doesn't quite know what they're doing. Decide what you can afford, and what you would be willing to spend. After I've gotten a price range I'd start looking for someone in that range. Then I'll get an idea of who the engineers are, what they've done, and listen to some demos. After that I'd go based on personal connection. I want to work with someone I can tolerate, that has the same views, and ideas about the music. Then go from there.
Good luck.