I use to travel with just maps (el-cheapo at the gas station), till I got somewhere where the map wasn't quite up to date and I wasn't sure where I was on the map. Then I got an excellent gps (garmin 76SCSx color map capable, 2 gig chip, etc). Worked great....except when you weren't moving much.... or when it decided to have a brain fart and locked up. For the most part, the gps is great, especially when you need to back track your way out.
HOWEVER, heard of a couple who got caught on a mountain top in a white out. Couldn't dare move around enought for the gps to lock on. No compass. Had to wait it out as there was only one safe direction down off the mountain and they had no clue where it was.
Always have a compass (an orienteering one at that). I have a Suunto MC-2. Make sure you know what the declination is for where you are. In my present area it is about 20 degrees east of true north. The gps (most of the time) will tell you where you are. A map and compass depends on you knowing where you are when you start and then you can plan where you are going (taking a bearing, working out travel times etc).
For professionals who depend on knowing where they are, carrying both and knowing how to use both is standard practice (when it counts, a back up plan is a good plan). Besides, learning orienteering and mapping out where you are going is fun.

The first time you get lost, it comes as a great big suprise. If you survive that, learning to get un-lost takes on whole new importance in your life. Sure did for me

Peace,
Narly