Unfortunately, Google Maps Navigation still requires an Internet connection, like most of the features of the Google Maps mobile apps. Navigation continues to work if you lose your Internet connection, but you can't change your destination or your route. Google Maps lets you cache maps, though they're limited to 50km x 50km and you can't get directions, use navigation or find local businesses. Nokia's HERE apps for Windows Phone, Android and iOS allow you to download full-featured country maps for free and use all of these features offline.
The good news is that Google Maps will soon add support for offline turn-by-turn navigation, directions, local search and it will even let you find more information about businesses. Here are some screenshots from the Google I/O Keynote:
According to Jen Fitzpatrick, Google VP for Engineering & Product Management, the new features will be released later this year.