You'd really need to find a GPS nav app that stores maps locally on the device.
I think I recently saw someone mention an app (on another site) that seemed to cache map data if you hit specific areas at the zoom levels you needed. I don't recall the name and will need to do some digging.
Results from a quick search. I haven't really checked these threads thoroughly and there are certainly plenty more threads to look at:
http://androidforums.com/htc-desire/77195-navigation-without-internet.html
http://androidforums.com/android-applications/72867-navigation-android.html
http://androidforums.com/android-applications/2149-caching-google-maps-use-offline.html
http://androidforums.com/android-applications/68140-any-off-line-maps.html
Most seem to offer the same suggestions. I seem to recall MapDroyd and OruxMaps after some additional pondering. No experience with either. I'm not off the network enough to make pre-loading (what some solutions require) worth the hassle IMO.
I don't recall when this thread was last updated but I was going to suggest it as a starting point. Locally stored maps should be a bullet point for any app that offers such a feature:
http://androidforums.com/android-ap...ps-thread-all-gps-available-android-here.html
Looks like it hasn't been touched for a couple of months now.