I did it pretty quickly. About 2 years ago, I started a small fence building company with my brother. I was doing some IM, and doing ok at it, but wanted a physical business to keep me in shape.
I added our business to Google Locals and found out that you can rank at the top of Google very quickly with Google Locals.
Within about three weeks, I had the number 1 spot for our company, just doing a little research and walking my way up the ladder. Then I figured I would offer it as a service to other companies, and I have been doing it ever since.
The thing that I have learned with any SEO that you are trying to do is this - The answers are already there for you.
For Google Locals
1. How is the number 1 position, number 1?
2. What makes that listing better then number 2?
3. What is holding the most value? Is it citations, reviews or address?
I will tell you a few things that I have learned.
1. Reviews has some weight
2. Address - Closest to city centers holds a lot of weight.
3. Local Phone number. Do not use 1-800 number unless you have to.
4. Citations are easy to get, just look at your competition and follow, then add your own and there you go.
5. Make your listing as complete as you can. Upload a video and some photos.
There are a few more tricks, but you can figure those out.
Hope that helps.