You could start with asking them for some client results that demonstrate their work which'll obviously be in the form of ranking positions and respective client url's. I'd expect them to work across different markets so you should be able to get a cross section of clients and start looking into the results they've obtained for the clients. This will give you some idea of how well they adapt to the varying differences in keyword competition through various markets.
Don't automatically assume when you're verifying those keywords that a high number of results (1 to 10 of about XXXXXXXX) is indicative of true competition as it's not that straightforward, some serps (search engine results pages) can 'appear difficult' if you just look at the possible number of results but may in fact be quite easy to achieve whilst others, may seem easy but in reality can sometimes have high competition and 'depth' for what seems on the surface as simple.
I think what 'is' important is that the most appropriate keywords that are targeted are the ones that will deliver the most benefit to the client without wasting any of the site's resources on non-performing keywords.
When you're doing your checks take a little time to look over the site concerned to get a good feel for what the site is about, this should put a few keywords/keyphrases into your mind then go and check the ranking based on those keywords and see how things look. Page 1 of Google is where the money is and the higher up the better.
Obviously beware of any guarantees, Google doesn't offer them up for grabs so how can an seo.
Find out exactly what the seo is going to do for you and don't be put off by jargon or waffle, a good seo should be able to explain everything for you in layman's terms.
Running off some quick questions..............
1. Ask them what they do about page titles & descriptions. They should be unique and specific to each and every page in the site.
2. Ask them what they do about session url's (assuming they do eCommerce sites). Ideally, they need to dump the query string and turn it into something short and meaningful. If it's a non eCommerce site then the urls would help if they're relevant somewhat to the page content.
3. Do they research keywords/phrases and how. There's some guesstimation in this regard but essentially, running a test bed PPC account which targets a keyword short list will provide decent data on ad impressions (users looking under those keywords) and is a very good guide to search volumes. Google keyword tool, Keyword Discovery and Wordtracker are three popular sources of information, expect very mixed results but some trends should emerge after staring at the numbers over a few cups of tea.
4. What do they do about external link building. Basically, you want 1 way, non reciprocal on topic (or as close to on topic as you can get) links from quality sources. Tons of junk links that are way off topic are a waste of time and resources. You'll also benefit from deep links so ask them about those and how they go about sourcing them.
5. Do they code spiderable internal navigation links into their sites. Internal links within a site count as well as external links so they must ensure that the search robots can find every page within the site from all links.
