In Minecraft 1.0.0, I was creating a redstone suicide cart. It go out well, but when I tried to make a hole, there was an abandoned mineshaft down there. I discovered the very first mineshaft. In 1.2 I don't hunt for mineshafts anymore.
So what's your achievement in older versions of Minecraft of discovering your very first abandoned mineshaft?
As soon as 1.8 came out, I seeked out new territories as I knew mineshafts would generate there. Found a swamp by a desert, started digging and voila, here we go. I thought I was incredibly lucky to hit one off the bat. Little did I know how frequently they generate. Now it seems easier to find a mineshaft than a decent sized cave, sometimes. I still remember how long it took me to find a canyon - an exposed ravine. The first ravine I found, right by that first mineshaft, was enclosed, and I took the time to dynamite and dig the upper layer so it is exposed to the air. Now when I find them, they always seem to generate in weird places - on the rectangular edges between different terrain generator areas, in the middle of an ocean with water streaming down, or one that had a natural bridge with a river flowing across it.