For me, studying a map in advance and reviewing it after a hike is very helpful in "cementing" in my mind where I was, direction of travel, which canyon we turned into, etc. Maybe try a small hike without your GPS? I think back on my career, which involved a lot of travel by car and plane, and remember riding shotgun with colleagues that relied solely on their Garmin to navigate. They often had no idea if they were headed north, south, one mile, or ten. When roadblocks or detours were thrown up, they were, truly, lost. I have an incredibly long way to go in terms of heading out on a long hike with nothing other than a compass and a good topo map, so I can't point fingers. But, as others have pointed out, I think it helps to pay frequent attention to landmarks. Turn around now and again to see where you came from. Maybe even point out the landmarks to your hiking buddies to, for lack of better words, "cement" the landmark in your mind. Good luck!
Stephanie and Blake Barnard