You can add a map field on products of course. The other part depends on google api and theme coding in order to create a search input to find on your “locations”. You need to be more specific on what is locations in this case. Something you add as a metadata to the map, like a name or title? Or by ID, or by product name…? could be many things if i started to think into this.
You may take a look into this things i guess:
http://jsfiddle.net/1dd3ss5p/2/
https://jsfiddle.net/upsidown/1svw299r/
Both has a finder, but they are searching for diferent things.