Different companies have different styles, just like different designers have different styles.
First thing to do: look through their portfolio. Really like the work they've done? Then you're probably also like the work that will do for you.
Then check that they are affordable.
Then run their site through W3 HTML and CSS validators. Validation isn't everything, but it gives you a good indication of whether they write clean code or not. By rule everything should validate 100%. Sometimes you may find the odd misbehaving script, or some funky CSS rules which are hacks for IE compatibility et al. All of this is not really a concern. If a website throws up 100 errors there is not really an excuse. If there's one or two there may be reasons why they are there.
If they do designs you like, if you can afford them, and if their code is clean: You got your new design company.
Talk to them, ask them if they've done similar projects to yours read the reply and you will feel if it is right or not.
Another approach is to browse through great design showcases. Example:
CSS Gallery | Css Leak
Find the ones you like, see designed them (often you will find this in the page footer), look them up. This also gives you a good idea of what's hot and what's not in (web)design these days. Then you also know a little what to look for when looking at designer portfolios.
Hope this helps
Cheers
Chris