Not sure about the mobile maps API, but in the professional version of the gMaps API, you can download all the map tiles and not have the need for a network connection to browse the maps.
If you just DL the tiles for the areas of interest, I'm sure it could be done on a phone. DL'ing the whole US might cause a storage issue for phones though (though I hesitate to say this since many phones now have rather large storage capacity and SD cards, etc.)
EDIT:
From the article:
Google Maps Navigation was built from the ground up to take advantage of your phone's Internet connection.
I think always having a network connection is sort of the point of developing this application for Android. Their address lookups are sent to Google's servers and the guy in that demo video is constantly mentioning "the cloud." I don't imagine this would work without a network connection since their intention is not to develop a standalone GPS device.
If it doesn't work off-line then it is far less useful. The problem is not so much that network connections are hard to come by, but that once you leave your little corner of the world they become stupidly expensive. I dare not think what the the bandwidth bill for using something like this for week abroad would be.
Google Maps Navigation is only available in the US.
I don't think it's really reasonable, at this point, to expect a GPS device to work worldwide. Are they supposed to store the world's mapping data locally? Google is still licensing their maps from Tele Atlas (TomTom) outside the US so I don't think it's even possible for them to provide navigation in those parts.
Storing all the worlds map data locally is unnecessary. All you need is to let the user download the maps for the part of the world he intends to visit before he leaves. If it's a licensing problem I'm sure it can be solved with money. I'll happily pay a reasonable fee for each additional country/region.
I don't think the licensing problem can be solved with money. TomTom owns the mapping data and obviously wouldn't let Google provide a navigation app since it would put them in direct competition with TomTom. That's why Google had to create their own maps for the US.
The map downloading model you're describing already exists and there are already plenty of other companies providing in-car GPS devices for that. I don't think it's appropriate to implement that sort of thing in a smartphone since the entire point is that it should always be connected.
