What can I do to help orienting myself in Minecraft Alpha?

Solution 1:

Place redstone torches on north walls. Redstone is quite easy to find deep underground and not required for much else.

Punch the ground directly beneath you. The break pattern is always the same relative to north.

Cheaper than torches, inlay the right-hand side of the floor with a dirt block every three squares. Build wide main corridors which you can follow back when you find one.

Grow a tree farm. Use the wood to make plenty of signs.

Design each area with its own character, so you can recognise them. Identical corridors are a good way to get lost. Place occasional markers, such as sand or wood.

Dig arrows into the wall pointing toward the nearest familiar spot. You can fill the arrow with dirt for extra visibility.

Create staircases upward occasionally. At the top, use excess stone to build a hut with a door and an observation tower. Use this to travel back to your shelter by aboveground when completely lost. Style your observation towers differently to use them as landmarks and build cobblestone roads between them.

Solution 2:

One thing I do is only put torches on the right hand side when exploring. Then to find my way back I keep the torches on my left. If a cave is big enough to need more than one torch I put the extra ones on the floor.

I also occasionally replace stone with cobblestones if I'm at a place where the correct way back is difficult to spot.