Building a kiosk locator feature for your site

Your company has just deployed 500 multi-purpose payment kiosks around the country, cash cows for the milking. Another 500 more are on the way, promising to bring in the big bucks for all the hardworking employees in the company. Naturally your boss wants as many people as possible to know about them and use them. The problem is that while the marketing machine churns away on the marvels and benefits of the kiosks, the customers need to know where they are located to use them. He commands you:

What you have is a database of all the 500 locations where the kiosks are located, by their full address. What can you do?