Patricia Hursh wrote a ClickZ column named Four Steps Every Business Can Take to Improve Local Search Results. The article goes over the what, why and how on Local Search. In short, how does one get included in the local results you see search engines providing? She recommends that you (1) update your business listings at Amacai, infoUSA, and Acxiom, (2) submit your site to local engines such as Google Local, MSN Local, Yahoo Local, Ask Local, and TrueLocal, (3) update your Internet Yellow Page listings at YellowPages.com, Verizon SuperPages, and SwitchBoard.com, and (4) make sure to have your address clearly listed throughout your web site.
Don't have time to do all of that, you can pay one of these two companies to do it for you; Relevant Ads or RegisterLocal. Also, if you are interested in understanding who local search engine powers who, see Bruce Clay's and TrueLocal's PDF chart.
Postscript Barry: Although Amacai is related to another sister company, Localeze, it does not actually manage local search content. Localeze, a completely separate company (Amacai is its subsidiary), manages local search content for local merchants.