If you are on Symbian/Windows Mobile you can install Garmin. It works the best! But the maps are a bit old.
If you are on Apple and jail broken you can use XGPS from Cydia store and download maps from google in offline mode.
If you are on BB RIM you will need WIFI/3g or crappy edge connection as there is no offline map app i know off which works with RIM.