I found a big cave system last night and got very lost last night! I was running out of torches so after finding a large cavern filled with waterfalls, so I started digging back to the surface.
Got to the surface and I thought I was close to my base, but could not find any landmarks. I left my compass at my base of course (will never do that again), so I wandered for a good hour before giving up, dumping all my cobblestone and setting up a temp base. Dug down to bedrock and got some redstone to build a compass.
I had wandered completely to the other side of the spawn point from my base! Now I did not leave any markers to my base, but I had a general idea of where it was. Took about another 30 minutes to find my base again, was starting to get nervous. Got my big haul of iron back safely in the end tho!
Here is the kicker. From my base I could see the spot I came out of the ground originally I was that close! I had walked the opposite direction...