I think the formula for Obsidian is moving water has to pass over still lava. Otherwise it turns to cobblestone.
I seem to recall reading that iron only occurs 10 blocks below sea level or deeper. But yeah, mineshafting is the way to go.
Everyone has their own mining method. I usually build a 3 x 3 shaft with a one block notch in one side for ladders every other block (just step into the notch and slide slowly to the bottom. Then like Reverend said, glass roof, and torches on either side. For extra safety I build my shaft indoors with a matching skylight in the ceiling.
When you hit bedrock, (about 60 blocks down), dig down as far as you possibly can til you hit unbreakable bedrock. Then count up 10 blocks. Between levels 10 and 16 is where you'll also find diamond and redstone as well as iron and coal.
At the bottom, I'll open up a 10 x 10 x 3 room and set up a crafting table, crate, and furnace, then every third block, I'll start a two block horizontal tunnel around the circumfrence of the room, all radiating out like the spokes of a wheel. Just be very careful where you step, as theres also lava down there.
Had my first wolf encounter last night, but I'll save that story for a later post.