Just got into geocaching also -- and had to go paperless -- I went crazy and got the Palm LifeDrive -- 4 gb of storage with the ability to add even more (not that you would ever need it) with an SD card. I also ordered TomTom Navigator 5 for it along with GeoNiche. Plan on using my explorist 600 for the bushwacking caches to keep the Palm out of harms way.
Bluetooth is a type of wireless connection --