My setup, Treo 680 with Garmin GPS 10x. For driving around, I'd use the MobileXT provided by Garmin. As for paperless Geocaching, and all-round simple navigation without the clutter of maps, I used GeoNiche for Palm.
MobileXT supports loading up the GPX provided by geocaching.com, and helps me to drive to the nearest carpark to the nearest cache site. GeoNiche, is a different beast altogether.
GeoNiche provides reasonable Geocaching support by providing a Java app that feeds in .Loc or .gpx files from geocaching.com, and you get the descriptions and comments as a waypoint notes. Decryption of hints is also supported. I find GeoNiche software to be an amazing tool for navigation. Light on resources, I found that GeoNiche will lock on to satelites almost 10 times faster than MobileXT. In fact if you launch GeoNiche first than MobileXT, then MobileXT will work quickly. One downside though, if you launch MobileXT then GeoNiche, you have to switch off the GPS 10x, then switch it on, else the GPS 10x will only speak in the proprietary Garmin format, unreadable by GeoNiche.
I might try out cachemate as a specific tool for geocaching, apparently, there's support from GeoJournal and other mac tools to export directly to cachemate.
As for the Mac side of things, I used GeoJournal, but really have no need for it other than use it to see what my options are, and to post a few photos of my finds.
Overall I like my setup, and I'm sticking with it.