I love minecraft too. thats where i have been. except its on xbox 360. they have a new indie game called fortresscraft. its the same as minecraft but its in its early stages. they are putting updates out all of the time. it still is pretty awesome though.
One time, in a brand new world, on my 3rd night, I was making a mine, so I had to make a staircase down to near bedrock. Right in the staircase, 5 blocks above bedrock, where I had not even meant to mine at, I found 8 diamonds!
Most players do not realize that you can be at any stage, even your first night, to go diamond mining. Just go about 10 blocks above bedrock, and give it a try!