I wouldn't dream of heading out with out a map and a sighting compass, and a small back-up compass.
I own a couple GPS units and I think they are great tools and a lot of fun. But if you are in a canyon or under heavy foliage, drop it, run out of batteries, or otherwise have it malfunction, y'all better have a map and compass. Learning to use a compass, triangulate your position and reverse bearings for your return trip are basic skills for foot travel.
I like to do a fly over of my hike with Google Earth and I have a National Geographic topo collection of my home state. Having some basic knowledge of the area can really help you stay oriented.
And that is the whole point. If you check your map as you go, the chances of getting lost are reduced. I enjoy the whole process anyway.
Most of the maps I use for Washington state trails are from Green Trails maps (
http://www.greentrailsmaps.com) and the scale on most is 1:69500. They make laminated ones that are they only way to fly. You can make notes on them with a grease pencil and they don't turn into mush on a long rainy hike. I do have maps cases and they are a pain compared to the laminated maps.
It's interesting to note that there are many threads hear on bushcraft skills and cutting tools, but this is one of the few asking about navigation. The first rule of survival is not getting in a survival situation and not getting lost is on the top of my list.