You can always go through a site like 99designs.com or another freelance site. The benefit here is that you can get an idea of the design prior to paying and also evaluate multiple designs.
If you choose to go with a freelance designer you select on your own, there are a few things you should do prior to engaging. First, look through their portfolios, you are looking to see (a) what their previous work looks like in general; and (b) if they have done similar work. This is important in that someone that can do great "graphics" work, may not be that skilled in layout for a site. You will also want to make sure their work is "original" and they are not just copying templates or other people's work.
Narrow it down to 3 or 4 designers from your search. From there attempt to contact previous clients to get references if possible.
Finally, before you engage anyone, try to have an idea of the look/feel you are trying to achieve. Do you already have a logo? Do you have a color scheme in mind? Compile a list of sites you like/don't like and why the site falls into a particular column. These questions will help the designer from shooting in the dark at the design and ultimately save you time, money, and revisions.
As for payment, never pay full upfront. Maybe half upfront, and half upon completion. Or if you can do thirds that is even better. A third upfront, a third upon receipt of a couple mockups, and the final third upon delivery.
Make sure you have outlined how the final product will be delivered. Will they deliver via a PSD and you are responsible for getting it converted into HTML? Will they deliver working/valid HTML? If they are delivering HTML and image files, make sure they are using valid CSS. You don't want to spend another day or two converting pages of tables into valid CSS.
These are just some basic thoughts, but should get you going in the right direction.