Over Christmas weekend I had the opportunity to use Google Maps Navigation on Android 2.x. I confirmed that Navigation works when you don't have signal. I'd heard that it caches enough of maps that it can idle without Internet access for a while. Of course GPS is still working during that time.
More than 10 miles of the last leg of my trip were without any cell phone access at all, no phone network, no Internet data access. Navigation worked flawlessly right up to the last turn into the destination driveway including the maps, turn by turn voice navigation, etc., etc.