A quick first night shelter, this allows you to spend more time on your first day collecting wood, sticks, cobbles, and et cetera.
Shovel (not required, but makes it MUCH easier to dig down)
Pickaxe (if you want to expand into the stone layer)
Dig a diagonal hole until you hit the stone layer. Feel free to dig beyond it if you want to start a mineshaft! When you get to the depth you want to be, stop and dig a little area around yourself. 4x4 is ideal. At night, block off the top with dirt or cobblestone. After you've built a house, you can expand this into a mineshaft for obtaining coal, iron, etc.