I've done this in a few instances and you'd have to build a custom search index OR create your own web part and/or filter to get this to work as you'd expect for the locations. With either solution, you need to get the lat and long of the place they are searching for, then get a list of locations close to that. This can be run this against a geolocation database or a zip code table that has lat long and city/state info in it. Then you need to order the results by distance, then display them.
If you're using SQL 2008 or newer, you can use the GEOGRAPHY spacial data type to get distance. You'd use it like so (of course your lat and long values would be input parameters:
SELECT *, GEOGRAPHY::Point(Latitude, Longitude, 4326).STDistance('POINT(44.9778 93.2650)')/1609.344 AS ProxDistance
FROM YourTable
ORDER BY ProxDistance ASC