Android comes with Google Maps and Google Navigator. They work with the phone's builtin A-GPS receiver.
Google maps is nice because its updated constantly with new data on locations.
The big downside to the system, is that it requires an internet connection to work, at least you need internet to calculate a route. If you lose connection en route, it'll still get you there, but you won't be able to set any new destinations.
It also chews through battery, so get a car charger.
I find I can use my phone most of the time for navigation, but I keep a garmin Nuvi on hand as well, for when I'm outside of coverage.