Bring a good topographic map or maps and at least one quality compass and know how to read and use both. The compass doesn't have to be expensive, since it doesn't have to do much more than point north accurately. And to complicate things, remember that the compass points to a different north than the map. (a 16 degree difference in Yellowstone!)
The key to not getting lost is to refer to the map constantly so that you always know where you are. If you know how to read a topo map well enough, a compass is usually only needed in terrain like Yellowstone to verify your direction of travel. This can often be verified from signs in the environment, such as position and movement of the sun, moon, and stars in the sky, river current, and even other less obvious cues which tend to be more art than science (but still work).
A GPS is fun and can often make navigation easier, but these can malfunction without warning. A map and compass is a necessary backup.
I've done things like walked down the wrong trail and even lost the trail entirely at night while going around a huge blowdown.
Ok, I think Ti is done now. Planning and preparing for a trip is half the fun. I hope you have a great time, and look forward to hearing about it!