Existen las 2 versiones.

Hay sistemas de GPS que toman los mapas online, como el que trae por defecto el Wildfire S, y por lo tanto necesita conexión a internet, y también hay sistemas de GPS que trabajan con mapas almacenados en la memoria del equipo, de forma que no requieren conexión a la red.

Para estos últimos te recomiendo Sygic. Puedes bajarlo gratuitamente en el Android Market y probarlo durante un pequeño período de tiempo para hacerte una idea.

Saludos.