How do I find Lapis Lazuli?

From the Minecraft Wiki:

Lapis Lazuli ... is usually found at a depth of 32 and below, similar to Gold. The highest concentration of Lapis Lazuli Ore is found between levels 17 and 19. At this level the concentration is about 0.075%.

Maps generated before lapis lazuli was added will have none of this ore unless new terrain is generated.

So go to an area you haven't explored before, and mine down to ~18 blocks above bedrock. That's where you'll find the highest concentration of lapis lazuli (about 0.075%).