Depending on your route, a GPS may or may not help you. I've been very, very lost riding bike trails in Germany. There were a lot of trails and they were poorly marked, if at all. The map wasn't really helpful either.

A friend of mine traveled the same tangle of trails last year with a top shelf GPS--- and got just as lost! If you're traveling service roads, logging roads, bike trails or cow paths, (and honestly, these are the BEST places to ride IMHO), you're off the grid. Take the best map you can find, ask locals for help and count on getting lost somewhere along the way. It's nothing to worry about, after all.