If you want diamonds you should mine as deep as possible, if you're not in the snapshots levels 1-12 (watch out for lava.)
The Fortune enchantment is great for getting more diamonds (and coal, emeralds, lapis and redstone) from each ore.
If you're branch mining (long parallel tunnels) you should have at least 3 unmined blocks between the tunnels (a tunnel every 4 blocks) in order to minimize wasted effort.
If you're not branch mining you should (at least if you're not in the snapshots), sure, if you're lucky you can find diamonds quickly in caves but slow and steady wins out in the end. Most cave don't go down far enough for diamonds and the veins you find are likely to have fewer ores (since some were overwritten by the cave.)
(Technically I believe the diamond ore is placed after the caves but it can only replace stone, not air, so the result is the same.)
Also, switch to better picks as soon as you have some extra iron/diamonds, better picks mine faster.
If you want to catch up extremely quickly, use this strategy found by Matthew Bolan. I'm not going to go too in-depth on how it works as he has a 40 minute video on it but the tl;dr is if you can find a swamp you can get stacks of diamonds in an hour without even having fortune 3 by just looking at the clay patterns. I recently used it on an SMP I joined that was already a few weeks old and became one of the richest players in one evening.
here's the video if you're interested:
Rollback Post to RevisionRollBack
Come checkout my Youtube channel with Minecraft / general gaming videos - C4lico