Mine in the southwest quadrant (positive x and z), twice as much ore there (explanation) Fixed as of Beta 1.6
- Become familiar with depths, see this guide. Iron lives under the sea level.
- Don't branch mine: don't listen to that guide, or this answer. Since you're looking for iron, I suggest trying caves.
The "mathematical analysis" is seriously flawed, because you're not looking to get every single ore in the block. Instead, you want to get as much ore as possible per second. This means that you need to see as many "fresh blocks" as possible per second. Let's look at one statement made in the analysis:
Not bad. With every 2 blocks destroyed (or 8 seen), we get 3.7% iron. Halve that to get the value of one block, which is 1.83% iron per block. That means for every 54 blocks of stone we mine, we'll get 1 iron ore.
Except, whenever you add a turn to your mineshaft, your digging causes you to see the other faces of the same two blocks you just saw. So don't add turns - which is exactly what a branch mine does every 4 blocks. Furthermore, when you do find ore in your branch mine, you'll dig towards your other shaft, and this will let you see some blocks that... you already saw when you dug that other branch. If you're going to shaft mine, make it one long shaft at level 14.
So what about caves? How many "fresh blocks" do you see per second in a cave? Well... a lot. To get an estimate, I started a fresh game on normal, punched a couple trees, a couple stone picks, bunch of sticks, a sword. Found a decent cave system. Coal pretty quick, sticks became a bunch of torches, I hear groaning. Strategy? Run like a boss, place torches, look at ceilings, floors, nooks. Don't stand still. Found iron? Great: spot check for monsters, then mine it. (Don't mine around it hoping for more - 98% of the time there isn't/it doesn't spawn diagonally. Just move on.) Hit dead end? Go back, seal the cave shaft up with a horizontal line of cobble, so you don't go in again. I got 54 iron in 10 minutes of caving. And a lapis block. The guide says (I wouldn't trust the math) that I'll get that much in 21 minutes using branch mines. Caves are better. Also, cave mining is much more fun.
TL;DR: Go a ways SW of spawn, find a cave system, go deeper than sea level. Run through it placing torches.