A mi me ha dado muy buen resultado inscribir la empresa en cuestión en directorios para negocios físicos, de forma que se asocie el nombre con la dirección (Páginas Amarillas, Lanetro, Qype...) Son las llamadas citas, que funcionarían más o menos del mismo modo que los backlinks para una web normal.
Después es importante que la palabra clave para la que te quieras posicionar o bien esté en el nombre de tu negocio, o bien esté en la descripción. Añade imágenes, intenta conseguir alguna opinión, y date de alta en el Local Business Center de Google con la misma url que utilices en la página de Places.
Ahora mismo no se me ocurre más, pero espero que para empezar te sirvan estos consejos. 😉
Un saludo!