Looking for a checklist, or comparison site.
SEO in my personal opinion, really is more of basics your web developer should be doing from the start of building your site. There are some optimizations you can do along the way if you're unable to make your URL's friendly or some of the other heavier lifting things, but why you would pay for this when you already had someone build the site is crazy to me.
The service part that I think I could see being worth paying for is market research about your site. I've seen a company that went out and found out what keys words were really the best for a sites content/market and helped to tailor the content of the site more accurately towards what their market wanted. In the end it wasn't so much SEO as it was just getting their site to match what people really wanted to find on their website. If someone keeps arriving on your site with the search term "How to boil hot dogs" and you're site only talks about hamburgers, then there's potential. However dumping "Hot Dogs" all over your meta data just to increase traffic is a bit of a jerk move and the main reason I hate these so called SEO-experts.
I think evaluating an SEO depends on your needs. SEO has and is becoming increasingly segmented, there are some that specialize in IA, some in link building, some in local SEO, some in content writing, some in video SEO and so on.
Google does offer their recommendations on "tips for hiring and SEO" http://www.google.com/support/webmasters/bin/answer.py?answer=35291
I think what most SEO companies do is one or more of the following:
to evaluate/find what are the keyphrases that could bring you most traffic from Google.
to adjust your site title/meta description and contents to contain the keyphrases of point (1).
to add links to your site on many websites/blogs/directories.
I agree with XOPJ that (1) and (2) should be done by the guy who made you the site. Obviously if you bought a 10$ website (or a free one) you can't expect them to have done it for you. I'm clueless about what SEO charges for (1) and (2), I would evaluate a SEO doing this based simply on how much my website performs better on Google search results for those keyphrases after his intervention.
About point (3) the added value of a SEO company could be to avoid you doing a tedious job that might not even bring you the expected results. The SEO company might aready know what are the websites/directories/forums/blogs where is simplier to add a link to your site with a NOT-nofollow link and maybe with some PR on those pages.
For point (3) you could evaluate a SEO job by paying him only after he submitted you the list of pages where he inserted a link to you site, the PR of each of those pages and the number of outgoing links from each of those pages. Keep in mind these values might change in time, if I'm able to place a link to your site on Microsoft HOME PAGE, but such link is removed after one week, it's not very helpful.