If your company has a bunch of store locations, please don’t hide that information behind a search form or a POST. If you want your store pages to be found, it’s best to have a unique, easily crawlable url for each store. Ideally, you would also create an HTML sitemap that points to the web pages for your stores (and each web page should have a unique url). If you have a relatively small number of stores, you could have a single page that links to all your stores. If you have a lot of stores, you could have a web page for each (say) state that links to all stores in that state.
Here’s a concrete example. I’m a big fan of Pinkberry because I love frozen yogurt: both the delicious treat and the new version of Android. But Pinkberry’s store locator page only offers a search form. Pinkberry has a url for each store (for example, here’s their page for a San Jose location). But because Pinkberry doesn’t provide an HTML sitemap on their store locator page, it’s harder for search engines to discover those pages exist. And in fact for the query [pinkberry san jose], Google does find the specific page, but it doesn’t rank as highly as it might; some other search engines don’t return that web page at all.
I was able to find a list of store locations on Pinkberry’s site, but it’s a lot harder to find than it should be. My advice to Pinkberry would be to add a sentence to their store locator page that says “Or see the full list of all Pinkberry store locations.” That would be helpful not only for regular users but also for search engines.
This was one concrete example, but lots of large companies mess this up. If you have a lot of store or franchise locations, consider it a best practice to 1) make a web page for each store that lists the store’s address, phone number, business hours, etc. and 2) make an HTML sitemap to point to those pages with regular HTML links, not a search form or POST requests.
By the way, Google does provide Google Places (formerly Google Local Business Center) where you can tell Google directly about your business, as do other search engines. But that doesn’t change the fact that you should provide a web page for each store–that lets anyone on the web find your store locations more easily.
P.S. If I were doing a full SEO site review on Pinkberry, I’d mention that they have a slight duplicate content issue, because they have a two different urls for their San Jose location. That’s not a huge deal, but employing the rel=canonical tag would allow Pinkberry to select a single, nicer url instead of search engines trying to pick between two identical pages.