As I work on my business site and other local businesses and read through the SEO world about what works, what is hot and newest trends, I find lots of literature about what to do.... but little about what really works.  I'm going to try and summarize a bit about what works for local SEO and where the clients might be located that can afford more significant SEO efforts.

Before starting - a little about my efforts.  About 5-6 years ago, as a business operator, we had a then five year old web site with a contact page for potential customers.  We were ignorant about the web.  We were finding increasingly more contacts through the web versus old school local media.  We looked up our rankings for various search phrases in different search engines and really weren't well ranked--page 4 or 5 or worse for phrases we could think of.  We saw competitors, on a national basis, very well ranked for various phrases and were aware some might enter our market and crush us.  We had to act.  Not knowing anything about SEs we read about Google and links in the business press.  When we contacted our web host about this and started asking about links to get higher rankings our host contact (webmaster) told us we needed to add contact... and links weren't necessary!

Needless to say we were very worried.  We didn't know who to contact or what to do, so I started learning about ranking.

I reviewed everything I could on the web, found out about SEO sources, got to some SEO forums and started applying what we learned.

Ultimately, we achieved first page rankings for our most competitive keyword phrases in all three engines.  For the #1 phrase we had highest rankings of #1 for the most competitive keyword phrase in more than one engine and similarly high rankings for secondary phrases.  These were industry terms, not industry terms with logical geographic descriptions.  

I studied analytics reports and optimized for logical geographic terms in combination with the business terms and generally ranked #1 for virtually every logical combo for a great variety of geo terms.  This all took time because I'm essentially a technical ignoramus.

Since then, I've assisted some other local businesses, have commented on local SEO issues across the web and have stayed on top of an enormous amount of local SEO commentary.  There are a lot of opportunities to follow these topics.  Some of the best sources IMHO include Greg Sterling's Screenwerk.com;  Bill Slawski's blog, www.seobythesea.com (great for patent work)   Mike Blumenthal's blog on Google Maps and Yahoo Local  www.blumenthals.com/blog  and a variety of others.  (Apologies to those I've not mentioned). 

So what happened to the local business over time?   From the time we started till the current period, monthly traffic has roughly quadrupled or quintupled  from 4k visits/month to 15-20k visits/month.  Conversions (contacts on the web) have increased at a similar rate.  Ultimate sales sources have moved from originally no web sales to a strong majority of sales from web visibility. 

We have had high rankings before the big onset and importance of Google Maps and subsequently have maintained high rankings, have experimented with IYP and other marketing sources, etc.

Of interest, current traffic trends and over the last couple of years have roughly been about 75% direct (bookmarked) and navigational (our home page or an internal page)--for the most part return visitors.

Of the remainder 25% it's mostly SEs heavily skewed toward Google.  Slightly less than 5% of the traffic is direct links, and of those I have searched aggressively to find highly relevant links that deliver convertable traffic (and searched for link juice!) but at this point conversions are more valuable.

Before getting into what works for the site(s) I'd like to cite one great source from a well respected SEO, who incidentally at the time, had to have seen about as many relevant local searches as anyone out there. 

This reference  http://www.seroundtable.com/archives/006710.html summarizes a discussion on local SEO from November 2006 Pubcon in Las Vegas.  Read what Jake Baillie, BakedJake had to say about "spamming the search engines".  At the time Jake ran TrueLocal, a specialty local search engine. 

He had to have seen about as many local searches as anyone out there.  My experiences agree with what he said.  Currently, even with the explosion of visibility of Google Maps, and all the advice about getting into Google Maps, I continue to agree with him.

Above all else he discusses expanding keyword phrase visibility for both business terms and relevant geographical terms.  Let me give an example from some searches I did for "used cars" and variations of that term in some keyword research tools and then for a couple of used car searches in my region and then I'll cite from my key business site analytics reports.

In the Google Adwords keyword tool, I looked up used cars and found after that term, a large variety of secondary terms (long tail terms), all which seemed to have relatively high traffic compared to the primary term:

For example, secondary terms include "buy used cars", "used cars for sale", "cheap used cars", "used car dealers", etc. There were also terms for specific cars:  used Honda cars, used Ford cars, used Nissan cars. There were also many terms where the searchers were geo-specific;  "used cars New Jersey", "used cars San Antonio", "Cleveland used cars", etc.

Take a look at Overture for used cars and the information is somewhat similar though more skewed toward more long tail searches with lots of different geo terms for cities and states.  And there is a lot of traffic there.

I then looked up (in Google) used cars Northern Virginia (where I live) and used cars Vienna Virginia  (oh boy, there are a lot of used cars dealers there). The used cars Northern Virginia search doesn't have a onebox map insert.  The used cars Vienna Virginia has PPC ads on top, then a large onebox featuring 3 dealerships, and beneath that the organic search results.

With the two different searches there were different organic results.  In general though, there were actual specific business websites, auto directories, a local directory featuring autos, yellowbook and yellowpages interspersed within the top ten. PPC ads included ads from particular makes of cars, specific dealerships, vertical directories, etc.

The topic is a very big ticket item for local sales and advertising. 

The phrases have a lot of competition.  The various advertising media, such as directories, and versions of IYP are spending a lot to get visible, but if you search through the many variations on used cars and attach relevant geographic terms to the searches.....no single competitive site dominates across the board.  The advertising sources, such as IYP and the directories cover some but not all of the variations on used cars and variations on geograpical terms.

Now for my business site SE traffic.  We see a most competitive term, and 3 significant secondary terms, and then about 10-15 less significant secondary or tertiary terms.  We get a lot of traffic on those terms, even without geographic combos. 

We then see an enormous variety of geographic variations on terms.  In my region the majority of geographic terms are state or city terms or their shortened versions;  Virginia, Maryland, Washington DC, VA, MD, DC.  We see searches for our business terms with town and county names and sections/sub regions--Northern Virginia or Southern Maryland.

I have spoken extensively with a webmaster who has lots of rural clients in a region where most of the geographic searches are via town names.  Gotta use a different strategy.

Of interest over several years of researching the vital keyword phrases about 1/3 of our traffic are the 15-20 vital industry terms, about 1/3 of our search traffic are combos of those terms with relevant geographic terms, and 1/3 of the traffic comes from other traffic (other content on the site) including a fair amount of traffic for relevant business terms with non-relevant geo terms (too far away for our very local business). 

Of more interest while the industry terms represent about 20 terms in total....the geo/industry keywords are ridiculously long tail.  For example if the single most popular term for a month might total 400 searches (an industry term) the single highest geo version of a relevant industry term might total 20 visits in a month.  Yet invariably we see virtually the same total.

From my perspective as a business operator, the terms that convert best are the combo geo/industry terms.  In our case they convert about 3-4 times as often as industry only terms.

Basically I'm probably speaking about 100-200 potentially convertible terms.

How do we do it?  Well fortunately on a local basis, there will always be holes in the competition--when there are a lot of terms for which to compete.  Even in the big dollar ticket/highly competitive used auto field....try a few different searches for some of the popular terms and the SERPs will show very different results depending on industry term and geo combination.

It all gets back to what Jake said: keyword expansion. It has to be done both with a long tail of industry terms and with geo terms. Jake was speaking to a universe of SEO practitioners. He emphasized PPC.  It's a great way to make money and cover all bases.  I have to add... optimize, optimize, optimize.  Do it on page and do it with anchor text for those different phrases.

Since these almost 6 months since Google Maps has become a more significant presence for local searches, I admittedly still can't determine how much of my traffic is seeing us via a onebox maps insert versus searches within Google.  I'm sure it's significant, but you should know that a lot of the geo keyword phrases don't generate Google onebox inserts.  Organic search still is more important in those cases.

Couple of other very important points:

Get into every SE version of Local/Maps.  Get all your information correct.  It will turn up great results.  Use varied PPC tools and study the reports from the engines.  Very valuable information.  Spread the keywords through every town in your region.  There are some nifty geo tools that will list every town in a radius anywheres in the states.  Then attach your business terms to the town names to cover a wide variety of search phrase options.

Get topical links and get local links.  Interview the owners of the business(es) you service.  They know more about the deep motivations that drive customers than anyone else.  They will help you come up with clever competitive ways to search for phrases that aren't obvious to the competition, the IYP's and the directories. 

Evaluate the advertising sources.  My business site outranks every version of IYP for every alternative search term, regardless of town, city, etc.  On the other hand, obviously yellowbook and yellowpages.com have put a lot of money and resources into ranking high for big ticket items like used cars in Northern Virginia.  If they are high ranked.....get advertising visibility within them.

The SEs and their Maps/Local versions use different algorithms.  I'm pretty sure that all versions of maps/local are going to see consistent changes and refinements on their algorithms over time as they are still relatively new.  (From Dec 06 to Feb 07 I saw my business site pop all over the place within the Google maps algorithms for potential geo search phrases).  For Google Maps, it seems to pay to use various other Google tools like coupons, Google base, reviews, etc. to improve rankings within Google Maps.

Who are the customers for significant local SEO services?  They have to be big advertisers.  You can already find them within the display ads of local versions of the hard copy YP, in display ads in local/metro newspapers, on local radio and local advertisers on TV.  They are already spending a lot.  Best of all their spending on old media sources is diminishing and they are all moving to the web.

Web 2.0 and the social component of the web?  I think this is virgin territory for local SEO but it will grow.  All sorts of businesses are on Myspace....yet take a look at Myspace groups for any region in the US and it is admittedly small relative to the whole.  On the other hand, my best conversions come from the aggregates of the 1-25 visits/month I get for every version of a business term and a geo term.  Certain aspects of Facebook are incredibly local.  If I had a business catering to young people in or around Boston, with all those colleges and young grads remaining in the area, I'd figure out multiple ways to get visibility there.

Get help from the customers who found the business on the web.  Where else do they go locally, or topically.  That is a great source for potential qualified buyers.  Survey them, or have the business collect the information while or after providing services.  Here is a great technique.  Get a hold of one of the data bases that collected the inadvertant AOL data dump last year they represented several million searches.  Search for relevant business terms for the business site.  Then go back and search by IP for what the searcher looked for before or after he hit some relevant terms.  What a great way to uncover underlying thinking patterns of potential customers.  (I believe I learned that from someone at SEOmoz! Last year!)

Above all else, focus on keyword expansion as Jake suggested.  I can vouch for that, based on my history in seeing a business site climb through the relevant rankings, increase traffic and conversions many fold, volume outsell my nearest competitors by about twice as much, compare my traffic to competitors from around the country and watch my business move from NO web to being reliant upon the web.