I play single player survival peaceful mode, so I don't have to worry about mobs. Nevertheless, it takes me ages to explore caves and mineshafts and I often almost get lost because of all the branches and side tunnels that circle back on each other.
I place torches only on the right-hand wall as I am going through the tunnels. This helps me find my way back.
I use mushrooms, torches, blocks of earth and fenceposts as breadcrumbs and sometimes put up explanatory signs
I've started "blocking" off tunnels that have been fully explored with gravel block - fencepost - gravel block. That way, I can still see what is beyond and the tunnel is still accessible.
I douse any lava I find, so lava is not an impediment.
Are there any other useful methods I am overlooking?
I don't only explore - I mine everything I come across, and fill up the holes afterwards.
The Meaning of Life, the Universe, and Everything.
I adopted the trick of placing torches on one side of the caves a long time ago. It lets you know very simply whether you're headed away from the entrance or towards it. However, some caves/caverns are so wide that having a torch on just one wall doesn't give enough light. I this case, I place enough torches to light the space properly, but I place the extra torches on the ground, not the walls. If I retrace my steps through an explored cave, and I see a torch on the ground, it's basically saying "I'm here purely to provide light - don't use me as a direction indicator".
I typically go in two times, once for exploring and lighting up the caves and once to actually do the mining. That way I can focus on moving quickly and gearing towards combat (not applicable to those playing Peaceful I suppose) and then a second time with nothing but a pickaxe to get all the goodies. So that strategy might not be useful for you
I also stick to using a block that isn't found in caves as my breadcrumb block. Anything easy to get in large amounts and is highly visible like sand, wood half slabs, or carpet. Then I don't need to be worried about not lighting a cave up enough to ensure I know which direction I am going.
Lastly, I'm not shy about making a staircase to the surface any time I need to, like if I do manage to get lost or just fill my inventory. It is often faster for me to go straight up and then head home on a surface level than climb back through the caves. Plus it only takes a couple of blocks to seal it up once I don't need it anymore.
I'm trying to wean myself off of relying on torches on one side, for the reason Saiph2 mentions, but also because sometimes you have caves with multiple entrances, or you join up with a cave you've already entered from another direction, and the lights get confusing.
I use two torches to mark the way back: one above the other, if I have to go up or down, or side by side, if it's a horizontal tunnel.
Non-torch breadcrumbs, kind of like what you mention. My preference is for a cobblestone pillar with a torch on one side to point the way back. I especially like this method when navigating the Nether.
Polished andesite, diorite, or granite. I can make it while traveling and it doesn't occur naturally, so it stands out as something I placed myself. I put a torch on one side, like in #2, to indicate a way back, or use it without a torch to mark a route I'm currently exploring when I'm making trips back and forth to clear inventory or pick up new supplies. In a pinch, you can also use three polished stones in an L shape to point to a direction if you are out of torches.
If I'm tunneling and find lava ahead or otherwise want to block off a passage for safety, I place a torch on the cobblestone or polished stone barrier to remind myself "don't break this wall unless I'm ready for danger".
When faced with multiple directions to choose to explore, I try to start on the same side each time. Since I place my torches on the left instead of the right, I also explore the left-most passage first when the path forks, then I come back and do the next, in order, from left to right. You would do the opposite and go from right to left, if you followed that practice.
In mine shafts, I try to place my torches in the middle of the ceiling support, instead of on the wall. Then, the way back is the path where the torchlight is visible, but not the torches themselves. I also use signs in mines, when things get really confusing.
Smelting stations. I rarely smelt while exploring, but when I do, I usually leave the furnaces. It's just another landmark to make navigation easier.
When I bridge across ravines, I usually add a cobblestone roof as well. Not only does that protect against creeper bombs or snipers from above, but if I'm in a different part of the ravine later, I can spot my obvious bridges easier and recognize that I've been here before.
I try not to kill flowing lava or water sources, but instead dig a small pit near the source and redirect temporarily with blocks, so that I can leave it as another landmark. Also, if I suddenly need water or lava, I can run back and get it.
I often skip mining until after I've lit up at least part of a tunnel, then mine on the way back. That way, I can get everything lit up and mark the correct path quicker, then mine in peace.
I find that I usually don't lose my way back to home base very often. It's usually finding my way back to where I left off exploring, or where I want to go next, or two a spawner I lit up and saved for later. The polished stone pillars or signs help a little, but often I have to take a break from exploration and just construct a straighter shortcut to make a frequently-used route less confusing.
I don't actually do much at all when exploring; I just barge through caves placing torches on the ground whenever it gets too dark to see well and kill any mobs I run into, often going through multiple passageways and intersections until I reach a dead end or one of those ridiculously complicated intersections where there are so many intersecting caves they form a large ragged chamber, then I backtrack and mine out all the ores. The only markers that I use are cobblestone pillars that I place on the surface to mark where I left off from a caving session and plan to return or found a new cave/mineshaft to explore later. I also carry a map while caving to see where I've been in general. I do tend to explore a cave system from the top-down, preferring to go through passages that go higher up if I start exploring them deeper down, as is often the case (I generally do not explore surface caves unless I've already explored around the area and come across them while passing through; any such unexplored openings are likely to be short dead ends and not really worth exploring).
How do I know where I've been before? Simple - there are torches everywhere and ores have been mined out. I do miss some areas but well over 90% (at least) of a cave system is fully explored; I often do return to the last marker I started at to make sure that I didn't miss anything nearby, particularly when I travel 100-200+ blocks away to the next marker. For some measure of my efficiency I occasionally mine more than a thousand ores per hour while exploring a cave or mineshaft network, and explore around 100 chunks (equivalent to a 160x160 block area) of the underground per 3 1/2 hour long play session.
Here is an example of the sort of caves that I regularly explore; not every cave in 1.6.4 is like this with the caves I'm currently exploring more like a typical scattered network in 1.7+ (1.6 does not just have bigger/denser cave systems, there is a lot more variation in regional cave density), with a ton of mineshafts intertwined with them (I've already nearly made up for all the rails I recently used on a 1474 block railway):
Yes, that is sunlight and snow nearly reaching lava level; some of the caves that I've explored have reached 50% air in a single chunk between layers 11-62 without the help of a ravine:
Note that most of the torches are placed directly on the ground, where they are most useful, especially in open areas like this; I only place them on walls to light up high areas or when there is water on the ground:
Due to their much higher frequency in 1.6.4 you can also find huge complexes of up to a dozen or more mineshafts intersecting one another (that's not a dozen mineshaft corridors - a dozen separate mineshaft structures, each with a dirt room in the center):
Also, these are some ravines I explored; I generally explore them from the top down unless they are small enough to light up by jumping up to place torches and/or don't have significant ledges:
Even the largest cave system that I've found (in vanilla) - with the equivalent of 1,400 chunks worth of caves at the 1.7+ cave density - only took a week to explore; you can also see how I go back to finish exploring areas I passed by while exploring away from my last return point:
While exploring this cave I set up several markers (while I record the coordinates I often do not need them as my map shows where I've been before and they are usually near the edges of the explored area; some of them are not returned to for a long time though; the southernmost marker shown was created about two years earlier):
-1177, 1445 (last marker I made before I found the cave)
-1321, 1721 (I returned to this one to explore the latest area)
-1008, 1765 (marks a mineshaft which was explored later)
-1368, 1866 (last marker I made before exploring other areas)
-1137, 1958 (marks another mineshaft)
-1065, 2056 (an old marker from when I explored the map to the east, I never returned to it directly but explored caves that lead to it)
This is was most recent marker I made above; the furnaces behind it were filled with iron and gold ore so I could compact them into blocks, saving a lot of room (9 stacks of ore = 1 stack of blocks. I also often set up furnaces inside of an easily recognizable cave/ravine/mineshaft center room or along the path to an area I'm exploring, which is how it is possible that I can mine several thousand resources per play session without having to return more than once or twice every two sessions):
Here is another rendering of the cave system; note the absence of exposed lava on the right half (at layer 20, where the density of caves stands out better. I did not use any mapping tools to view the caves until I finished exploring them, I even made a copy of the world and deleted all unexplored chunks so i would not see anything I haven't explored yet. For the renderings above I used a utility that only renders caves if they have torches in them; I removed naturally generated torches from mineshafts in my worlds so they do not show up until I explore them):
For comparison, this is the entire world, again with unexplored chunks trimmed away (after I explored a bit more to the west of the cave shown above, which is near the bottom on the left side; below that is a railway to a new base I recently built. The explored-only area measures 6400x5680 blocks):
Likewise, this shows what I explored in the first 5 play sessions I spent caving in the last world I made (minus the branch-mine; I branch-mine to get my first resources since it is far more efficient at finding diamond, or in this case, a mod ore), which includes 4 mineshafts, several smaller/scattered cave systems, a large cave system, and 6 ravines. In this case I did not backtrack since I was pretty sure that I'd explored everything around the previous return point (in two of the frames you can see a diagonal line marking a staircase to the surface appear to the right):
I just focus on one task at a time. If I need to light up caves and smash heads, I'll just craft half an inventory's worth of torches and a bunch of swords and dive headfirst into the cave. I just keep going until I have to turn around and backtrack, picking a dark opening I haven't followed yet. If I feel like I strayed too far (or if I checked coords and discovered I truly did), I just drill up to the surface, make my way back to base/the cave entrance, and start over. When the cave is thoroughly lit up or when I run out of torches, I go back to base and change out gear for mining. I then enter the cave and locust the hell out of it.
Many times the cave intersected part of my (intended) build, so in addition to the ores I'll probably do some trash-block collecting as I do build-work. Cobble generally gets smelted back down to smooth stone and I fill in whatever caves are too close to the build. Some of my most mature worlds have been lighting up caves for thousands of blocks in all directions using the same 500 torches (waste not want not, lol).
One additional tactic I've taken to using (mostly because I play modded and thus have all these things conveniently at-hand within the minimap mod) is to keep track of where I've stopped doing particular tasks. On the surface, if I'm looking for a particular biome but haven't found it yet I'll note my position with an "explore stop" so I can quickly get back to that point without wasting time on stuff I forgot I explored earlier. I do the same with cave lighting and ore collection.
Only one tip from me that's actually useful. Follow one path to the very end first. Then come back and start again, but instead of going back to the end of that one particular tunnel, follow another one closest to the original one and keep expanding.
Once I am late enough in game, I never go into am mine without a few extra stacks of iron and some extra picks and swords.
Why not use diamond gear? Particularly with Unbreaking III you do not have to bring more than one of each item; I'm probably the only one who does enough mining to wear out an Unbreaking III diamond pickaxe (averaging 6248 uses) in a single caving trip (I mine an average of about 4375 blocks per play session and spend up to two sessions per trip). Of course, there's also Mending but it is wasteful to use it on iron gear when diamond is better in every way (I still play in 1.6.4 so I can trade emeralds for all the diamond gear I need, negating the rarity of diamond; renaming an item lets you repair it forever so all I need to bring is an anvil and items to repair my gear with as needed).
Also, why bring extra iron when you can easily mine far more than you can ever use? Mining 4375 blocks would require about 52 iron for pickaxes while I mine around 15 times that much - sometimes much more; here is what I got during a recent play session, which was spent mostly exploring mineshafts (I've found at least 5 directly interconnected so far, which is not a very lot by 1.6.4 standards, where in one seed I found what could be as many as 30 in a chain more than 1000 blocks long):
Note that I use a mod so I can craft 9 rails or 4 cobwebs into one block in the same way you can do with minerals and string (prior to this I used non-Silk Touch shears and crafted string into wool; either way I only collect the cobwebs around cave spider spawners). Including the coal that I used, which is the only resource that I used any of, I collected well over 6,000 resources and other items (for all other mineral resources I crafted more into blocks than mined as ore due to what I found in chests; even when accounting for the iron I used early on in this world):
Also, this is what I've mined overall...
Note that many of the iron pickaxes I've "used" came from minecarts; I give them level 1 enchantments, combining them to as high as Efficiency III and Unbreaking III, and use them to dig tunnels for railways instead of using my diamond pickaxe, though I did craft a lot (most of the ones shown) before I started using diamond tools (conversely, most of the diamond pickaxes I've "crafted" came from villager trading, which counts as crafting the item; the number of swords crafted is low because I used individual diamonds for repairs until I started trading, and even then I have to kill chickens to wear it out enough to lower the cost below 40 levels):
I've also crafted more than half a million torches and mined more mob spawners than emerald ore (the game does not normally show them in stats which is a bug that I fixed; there is no reason why they shouldn't show up). Note that the amount of moss stone that I've mined is equivalent to 1253 dungeons (48 moss stone each when averaged across each size); yes, all the remaining spawners would be cave spider spawners, which are by far the most common type of spawner, accounting for 7 out of 9 that I found in the play session shown above: