I should have been more clear when I stated unless you store your maps on the SD card. As Harrell clarified, you need a data connection for the maps, be it during the trip or before.
The map cache (from the maps ap) is stored on the sd card in
/sdcard/Android/data/com.google.android.apps.maps/cache
YOu can see your cache using an explorer type program or you can see the size of the cache in the maps apk submenu. By and large the size is relatively small for the road maps or terrain or satellite imagery, as compared to the old style of .jpg or .tif type map tiling storage. And a fairly large area is indeed downloaded to cache. But I have seen an anomly in my limited testing.
If you open the maps program and have data enabled (3g/wifi) the map set will be downloaded and stored on the sd card. If you turn off your data connection and pop back into maps, you can scroll around in the map set that was downloaded. But, if you zoom down very far, I have seen areas on my phone with degraded resolution. In the old way of using tif and jifs and jpegs to store maps on other devices (and even the droid with certain programs) the resolution or zoom level was accomplished by downloading a map set to correspond with the level of zoom you have chosen. The google maps program cache file images are encoded into the program format so I have not been able to see the structure to understand if the old way of sets per zoom level structure exists, but you do need to play with the maps of the area that you will be needing to ensure that you get the correct level of resolution for the zoom level you will be wanting.
I do not use Navigation, just the main mapping program and other stand alone packages, but back to the first point you will need your data connection to get things loaded, and you will need to download and test to make sure you get a clean and visible map set at you expected zoom/resolution level.
Craig