Ok, I see some people are having trouble finding a decent star location.
So...
Never travel to far away from the spawn point, if you die, you'll spawn quite far away, I spawn right inside my property
There are always places to start building everywhere on the map, always!
As a rule, first thing is finding 3 to 5 trees and get some wood, you'll need that wood to make a pickaxe to get stone and coal asap.
Second thing is finding a cave or hillside to make the first hideout pretty fast, in case of a cave, block the remaining of the cave, so creepers (and those exploding penises) don't appear from behind (argh, this sounds ugly)
Make a few torches, yesterday was testing minecraft on a recently installed linux, and in about 5 mins I already had a home in a cave with coal around, trees and dirt to make the first walls.
In my working map, I spawn in my yard, inside my walls, in case of death. If spawn at night in a distant spot, you may and mostly will die again from the creepers if you have to travel long away to safety.
I hadn't the time yet to make a video of my workings, but will soon I have the time, atm I'm laying down lots of rails
The servers aren't up yet, due to the simple survival bug of... not dying and not be able to kill creepers or any other entity in the game, all are in god mode.. bah