In town, my Garmin eTrex takes a good minute or two to aquire enough satellites to start navigating, and a minute or two more to really get the accuracy rate down around 20 feet or so.
I've only gone out to find two caches, but I turn the GPS on in the car when I leave my house, and place it on the dash. That way I get to track my entire trip, and when I show up to the cache site, the unit already has locked in on the satellites pretty good.
The unit is supposed to run for 22 hours on one set of batteries, and after much playing around in town and a solid 7 hours straight of GeoCaching last weekend without turning the unit off, I'm inclined to believe it. So just turn the unit on when you leave the house, and bring some extra batteries just in case.
That's what I'm going to do on my future GeoCaching outings.