Look under "Cache Settings" in Maps. There's a checkbox for "Prefetch on Mobile". If it's off and you're not using Maps while on Wi-Fi then I wouldn't expect much caching to happen. You can also see how much data Maps has cached.
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.