Google Maps doesn't cache more than a few tiles so it's totally useless. There are a number of apps in the Market that will download maps locally - one downloads Google Map tiles illegally (with mixed success) and the rest I couldn't get to work.
Do you have any advice or experience you can share?
I don't have a data plan and I find caching works well on my Nexus One when I ask for directions before leaving the house. I haven't tried it on a long road trip though. For comparison, the cache size on my phone is 37M now.
I'm not sure how legal Google Maps caching is, but in my experience OpenStreet is a decent alternative in most of developed world.
Having experienced this, it's really annoying when Google Mobile Maps on my Blackberry insists on redownloading the map of my neighbourhood for the fiftieth time. It's extra fun on EDGE.
I also have no experience with possibly caching directions, being a man and having never needed them ;)