Any GPSr will perform the tasks you mention, but BT will give you more flexibility, for example putting the receiver in your backpack while carrying your PDA. I do exactly this when hiking with my Emtac and my Tungsten T and a raster mapping program. For turn-by-turn when driving, Destinator on my Axim points the way very nicely. An iPAQ will do just as well.
You do not need to subscribe to a service, the GPS signal is free. (I'd like to take this opportunity to thank the American taxpayers for funding this excellent service for me. Cheers, guys!).
You'll need two different types of software for turn-by-turn routing when driving, and when using maps while hiking. Note that the maps in the latter will need to be georeferenced, that is, calibrated so the software knows their latitude and longitude coordinates.
Well, that'll get you started, Bare. Another site outside this one that's worth checking out for GPS basics is
Dale DePriest's page, and for software and hardware reviews you might like to look at
GPSPassion and
Pocket GPS World.