I would have a single locations page that lists all of your businesses locations by city, state.
I would link the city, state to a landing page for the specific city,state.
Each city, state landing page would have a unique, URL, title, headings, content, etc that would use a format like Keyword | City, State | XYZ Company - because if someone Googles your company name, you should already come up... it is more important to have the keywords, then city or city, then keywords in your title - do some keyword research on this to see which is best for you.
THEN register each of those city,state landing pages using GetListed.org - this will help you build up your local presence in those areas since you have a physical office location.
If you wanted, you could do the footer idea... I think that gets to be kind of spammy, but I guess it all depends on the industry and the number of locations.
Hope that helps.
Mike
