Hola, si usas el google maps, necesitaras estar conectada a internet para usarlo, con lo que si no tienes paquete de datos contratado, que cuesta dinero, te van a cobrar por cada conexion que hagas cada vez que uses google maps.
Hay aplicaciones que no se conectan a internet, pero que son de pago, con lo que pagas de todas formas. Sygic gps es la aplicacion, tienes 7 dias para probarla y te descargas los mapas, con lo que no tiene por que conectarse a internet cada vez que lo usas.
https://market.android.com/details?id=com.sygic.aura&feature=search_result
saludos