You could check that they've done the SEO as well as it needs to be done ... if you have entrusted it to a room full of graphic designers and coders, don't assume they know how to spell.
You should sign up for a Google account and then monitor your site through Google Webmaster Tools. This takes a few days to gather data and get working but it will show you what the top keywords on your site are (this can be very revealing, especially if it turns out the top keywords words actually used on your site are not the ones you thought they were). It will also tell you where on the web other sites are linking to you. You should spend some time looking for places you can get a link to your site (non-spammy, of course). Links to your site are part of the ranking process.
Other than that I'd say:
1. Sign your business up for a Google Maps entry if you possibly can. Searches that have a relevant geographical location often throw up a Google maps summary at the top of page 1. We got our B&B onto the first page of Google results within a week by concentrating on giving it a very thorough Google maps profile.
2. Put a blog on your site and update it regularly. Google loves sites that are obviously active. Refresh the content on your main pages as often as you can as well, for the same reason.