The absolute basics
Move around with the WASD keys, press space for jump, Q to throw away what you're holding and I for inventory. Use the mouse to look around. Use the left mouse key to hit stuff, and the right mouse key to interact in other ways.
It is recommended to start a single player game to get the feeling of things.
First day: Shelter
Look around you - this is your world. Run around in circles a little bit to get the feeling of things - but don't stray! The spot you start is where you'll respawn if you die, so it can be handy to start your career here.
Walk up to a tree. Point at the trunk and hold the left mouse button. Your character should start hitting on the trunk. After keeping the mouse button depressed for a few seconds, the section you're pointing at should pop loose. Knock loose all pieces of trunk ("log" from now on) on your tree and collect them by going near them. You should now have four of five pices of log in your inventory at the bottom of the screen. As you might have already tried, you can use on log to beat on the tree with instead of your hands - doesn't matter.
Open up your inventory, note that you've got a "crafting area" at the top. Put the logs in one of the spaces. On the right you should see planks. Collect all the planks in a stack. Now take four planks and put them in the crafting area. Take out the table you just created. This is a crafting table or workbench. Put it in your hands and exit the inventory. Right-click to place the workbench in the world. Right-click on the crafting table, and you get a 3x3 crafting grid. Now you can make bigger stuff.
Make some sticks from your planks: Put two planks, one above the other on the crafting grid. Take the sticks. Put one stick in the center, and another in the bottom center of the crafting grid. Put three planks over these; one in the top center, one in the top left and one in the left center. You have now made an axe. Equip you axe, exit from the crafting table (Escape key) and really go to town on the other trees nearby. You'll need 15 logs to make a small cabin for shelter.
When you've collected enough logs, convert them all to planks. Find a small flat spot and plonk down the footprint for a 5x6 cabin, with a one block wide opening. Make your cabin two blocks tall, and cover it with a roof. Leave an opening two blocks high for the door. On the crafting table, arrange a 2x3 grid of planks, making a door. Equip the door, and put it in the opening by right-clicking. Now you have a viable shelter for the night, to keep you safe from monsters.
Now you are free to use the rest of your day. If it's late, gather your belongings and spend the night cowering in your dark (but safe) cabin. Come daybreak, most of the monsters are going to burst into flames. If there is daylight left, on the other hand, it's best spent looking for coal. A stick with a lump of coal on top will net you four torches on the crafting table.
The easiest way to find coal is often exposed coal seams on cliff faces. But you'll need a pickaxe to mine it. A wooden pickaxe is made with two sticks for a handle, same as the axe. Three planks are placed on the top row, forming the pick head. Grab your newly crafted picaxe and start looking for exposed coal in the surroundings. Don't lose your bearings! Use the clouds to orient yourself. They always drift due north. Coal seams look like rock with black spots. If you find some, excavate it with your pickaxe. Pick up the black lumps that are dropped when the rock breaks. Use your pickaxe to break some rocks as well; you'll need eight of the resulting cobblestone to form a furnace, and more for stone tools.
Go back to your cabin. Craft some torches. Craft a furnace (eight cobblestone in a square) and put it in the corner of your cabin.
Your actions the first night depends on wether you've got some torches or not. If not, then cower in darkness until daybreak. If you did manage to find coal before nightfall, then you can start a mine below your cabin.
To start a mine, dig diagonally downwards, making steps for yourself. After a while, maybe 20 blocks down, dig an exploratory tunnel horisontally. Put up torches once in a while as you progress. Collect any coal and iron ore you run across. Craft stone tools when your wooden tools are worn out. Smelt your iron ore in the furnace, using coal or wood as fuel. Keep going until daybreak.
From here on out, everything depends on you. Some people work on their dwellings during daytime, some explore. Some people mine during the night, some do interior decorations. You can liberate outdoor spaces by putting up a wall and ensuring that it is well-lit. Monsters won't spawn in the torchlight.
You can be a farmer if you like, growing wheat, reeds and cacti. You can join a multiplayer server and play with other people. The sandbox is yours!
The map ceiling (at which you can no longer place blocks or drop items) is 64 blocks above sea level and 128 blocks above the bottom of the map. However, bedrock randomly occupies the bottom 5 layers of the map, so it is possible your maximum building height could be only 123 blocks high.