Basically, it's a game in which you can do whatever you want. There are two moeds in which you can play - Survival and Creative. In Creative Mode, you have access to (just about) all blocks and items, to place at will in whatever quantities you like. You also can't be killed by monsters or whatever. This is the mode for people who want to just mess around building uber stuff (when gathering the resources in Survival Mode would be too much hard work, etc) and generally be cretive (as the name implies). It can also be for people who want to experiment building something that would require a lot of resources in Survival Mode and they want to test it out in Cretive first before they commit to it in their "proper" game. There's also a third mode, Adventure Mode, to which you can set yourself via a typed command in-game. In this one you can't break or place blocks - it's intended for people playing through custom maps made by other people (so it feels a bit more like an RPG and you're not tempted to cheat by breaking walls, etc(
Survival Mode is the "proper" game. You spawn in a randomly-generated world with nothing and must gather resources etc to survive, build yourself a house (or dig a cave, or otherwise construct for yourself some kind of base/shelter), and generally live in the world. Everything is made of blocks - the ground, the trees, the water, etc. You acquire these blocks by punching them or hitting them with the right kind of tool - you need a pickaxe to mine stone, for example. You will start by punching trees to get the wood blocks, which you can then craft into a very important block called a crafting table. You can then place this on the ground and access it - to craft stuff, you place blocks in the grid in the right configuration. You have a crafting grid in your inventory but it's only 2x2 squares and there are many things you can't craft in a grid that small. The grid on a crafting table is 3x3, enough space to craft anything. A good early step is to grab some wood to make a crafting table and create a wooden pickaxe - this is enough to mine stone, which you can then do in order to make yourself a stronger stone pickaxe. This is strong enough to mine iron ore, which can be smelted in a furnace (crafted from stone) to make an iron pickaxe. There are other tools you can make - shovel (for dirt, sand, etc), axe (for wood), and hoe (for tilling dirt to convert it in to farmland to plant crops), and swords (though they're obviously weapons rather than tools). Anyway, you'll be wanting to find some coal in order to mine that and use it with wooden sticks to create torches, which you can place to light up the area.
You have about ten minutes before it gets dark (when you load into a new map it's always dawn). Monsters (such as zombies, spiders, and the iconic creeper) spawn in the dark, so you need to get yourself somewhere safe before then, even if all you do is dig a little hole and hide in it (your character is two blocks high). It's possible to craft a bed (from wood and wool, the latter most commonly acquired from sheep) in order to rest in it and skip to morning - note that you can only do this in multiplayer if everyone sleeps at the same time. Using a bed (even if you're in multiplayer) will reset your spawn point to that bed's location, so if you die you'll respawn there rather than at the point where you first entered the world.
That's pretty much the basics, really. Once you've got yourself some kind of base set up, you can set about enhancing it (you know, making it look a bit better than a dirt shack/hole in the ground, etc), planting crops/breeding creatures for food, going underground mining and exploring (there are randomly-generated cave systems and abandoned mines and stuff which can have chests of stuff in them), building a portal to the Nether (a world of fire and lava and stuff with lots of ways to die horribly…more so than the surface world, but also containing plenty of handy items/resources that you'll probably want for stuff), killing monsters to get exp to spend on enchanting your gear (tools/weapons/armour) with cool properties (once you've built an enchanting table)…ah, there is so much stuff you can do!
I did actually write a newbie guide to Minecraft a while back. It's at minecrafttips.com if you wanted to have a more detailed look - it has screenshots and everything :). It was done before the last big patch, though, so some of the most recent stuff (such as horses) isn't mentioned in it. It's enough to give you an idea, though. There's also a video series on YouTube by a group called the Yogscast - I was rewatching it recently, actually…it started back when Minecraft was still in Alpha so there's loads of stuff that isn't in the game yet at that point. What else…oh yeah, there's a free version to download somewhere (I think there's a link from the Minecraft Wiki), called "Minecraft Classic", I believe. It's an older version of Minecraft so lacks many of the features of the current version, but it's enough to give oyu an idea - playing this after watching the first few Yogscast vids was enough to convince me to get the game. I've had it since Beta 1.8, a couple of years ago. Good stuff!
Whee, long post, and probably more than you wanted to know! Oh well ;).