Well, after setting up my comfy hobbit hole, I dug straight down in a 10 x 10 area to make a huge mineshaft and lovely stairwell... to hell! After that, I just started digging outward in various places about 10-20 blocks above the bottom and try to follow caves whenever I run into them. I use a helluva lot of torches, as I like to keep the randomly-spawning mobs to a minimum while I'm working. Coal isn't super-plentiful, but I have good supply of stacks, and the only other thing to use it for besides lighting is MINECART POWER, so I'm fairly generous with torches.
Gold is rare, but that doesn't bug me much, because I found enough for a couple of clocks (which is basically the only thing to do with the stuff other than pimp things - just like the real world!). Obviously having a boatload of diamond would be cool, but I have a little to play with (12 so far, made the obligatory jukebox and a sword, sitting on the rest for now), but it's really iron that you need a LOT of. I mean, it's something you can use almost as much as WOOD if you have it, and that's saying something. I'd swap the incidence of redstone with the incidence of iron in a heartbeat, if I could.