The offline map and navigation capabilities of Google Maps are so limited that they're of little use yet. You could pay for apps like Route 66 or Navigon, or you could wait until someone ports Nokia Maps to Android if that's ever gonna happen.
Enter OsmAnd. It can use the online maps of Google, Microsoft, and others, but its unique selling point is the combination of locally stored maps from Open Street Maps and true offline navigation.
Update: the free version of OsmAnd has offline navigation too.
Map rendering is a bit slow and the navigation part is still under construction. One way streets and roundabouts can be a problem and the routing can take strange twists and turns. Since the offline maps come from Open Street Maps the quality varies wildly. They're OK in the northwest of Europe and the heavily populated parts of the USA, but outside the major cities in the rest of the world you'll find that many streets are missing. But hey, it's free, and you can always help OSM improve their maps!
• OsmAnd+ (free version at xda)
• OsmAnd (Android Market/Google Play Store)
• OsmAnd at osmand.net