Google tiene distintas APIs que te permiten ubicar un lugar en el mapa de distintas formas, por coordenadas geográficas, por direcciones, etc....
http://code.google.com/intl/es-419/apis/maps/index.html
Con la que mas te guste tu puedes programar lo que deseas de una forma mucho más facil de lo que era hace algunos años.
Es como tu indicas, una base de datos con la información de los restaurantes incluyendo "por ejemplo" las coordenadas geográficas (que el mismo google Maps te da) y un archivo denominado "API" que se encarga de procesar la info que le des para mostrar el punto correspondiente en el mapa.
Saludos.