1.
Get a bucket, fill it with water or lava. Lava is easier to see, but water is safer and allows you to travel up and down without taking damage.
Get a bunch of sand. Build a 1X1 tower until you reach the top of the map and destroy one block of sand. Jump up and dump either the water or lava on top of the tower. The water or lava will flow down and create a very easy to see marker.
If you used lava, make sure you have a pool of water to jump into. If you used water, just flow down safely. It might just be easier to use dirt with lava so you can destroy a block under the one you're standing on to place the lava so you don't land in it.
2.
Build along the water and periodically place light houses to mark your path. When you find a mine, make a grand entrance with lots of torches so you can see it from far away. If you have supplies from the Nether, you can also use burning netherrack or glowstone as they're brighter.
3.
Make maps and create large, obvious landmarks so that they show up on the map.
4.
Google Minecraft Cartograph. It will give you a good impression of your world. Torches show up as bright yellow dots, so it's easy to find things on the maps you generate. Fire and glowstones don't show up, however. I don't think jack-o-lanterns do either.
5.
Place cobblestone behind you as explore a mine. Have all cobblestone meet up at the central vent leading to the surface. You should never run low because there's literally stone everywhere underground.