I've used both an hw6955 iPaq (which has a built in GPS) as well as a standard Garmin E-Trex (the yellow one).
I recommend that if you are going to use a PDA for paperless caching that you buy a separate unit. The handheld units are far, far, far more accurate than PDA GPS', and the refresh speed is much quicker which as any geocacher knows, is crucial when you're in an area with a shotty satellite signal.
The PDA GPS' are very good to get you in the general location of the cache and function excellent for turn-by-turn driving directions, they just do not have the quick-update capability of the handheld models yet.
That could change, though, with newer software stripped down for speed. My iPAQ is brand new (Oct 2006) and just doesn't like quick updates. I have located geocaches with it in good-signal areas, but it seems to require many more satellites to get a solid fix at times. BeeLine GPS looks like the software of choice for the PDA.
Good luck!