If you need a web designer, I would start with any designer you might have a personal connection with (even if it's a friend of a friend). Those are usually the situations that work out best in my experience. Otherwise, try putting up a Craigslist post for a designer in your area or Google for a designer in your area.

As for cost, it really depends on what the state of your current app is (i.e. what does it look like now, how complex is it, how unique do you want the design, and how compliant do you want the site (flash/no flash,png's with transparency or just jpegs...)). Personally, I'd try to steer clear of anyone who quotes you a price without really examining the site first.

However, so as not to just brush off the price question, I'd charge anywhere from a couple hundred for a crazy easy redesign to a thousand for a more conceptual and custom design.

Deliverables: You'd want to get the CSS file obviously, any additional IE style hacks that may be contained outside the main CSS file, and all associated images. And the flash stuff if there are any embedded flash files (I'm assuming that for a webapp, you're not referring to a full flash site, because that would be ludicrous and highly unusable).

Legal: Make sure that you have a fully "Contractor" arrangement in place and that there are no ambiguities that could cause the person to be confused for an employee, because the IRS doesn't like that much. Also, try to get full ownership of the artwork if possible, so that you can reuse images on print stuff later if you want to. I always give my designs to the client to do with as they please, but it's not unheard of for them to retain ownership. Either way, it should be outlined in the design contract.

Wow, that was long, but hopefully it answered your questions.