Mining, also called hashing, is the backbone of the Bitcoin network. It is the magic that moves money from person to person securely and ensures that your Bitcoins are owned by you.
A hash is a one way deal. You put some data into a hashing algorithm and a really huge and hopefully unique number pops out. The same input data with the same hashing algorithm will always produce this same number. The "one way" part means if you have this number you can't go back and get the original content from it.
Deciding on some features this huge number must have makes a nice little puzzle for a computer to solve. Namely, the resulting number must be below a certain given threshold called "difficulty". The larger the difficulty the fewer solutions exist to the puzzle.
Because of the one-way feature, you can't just take any old random number that satisfies this difficulty and then work backwards and get the inputs that supposedly "created" it. You absolutely must start with the inputs that connect this puzzle to the entire history of Bitcoin, run the algorithm, and see if the results satisfies this puzzle. This is what is meant by "work" when someone says "Proof of Work".
The "proof" part is when you say "here's the inputs that connect this block i made to the rest of Bitcoin's history, and when you hash it the result that satisfies the puzzle criteria".
If you proved you solved the puzzle using the hashing algorithm, ding ding ding congrats you just won yourself 25 shiny Bitcoins.
The kicker is that the puzzle is hard. Difficulty is adjusted when people add hardware to the network so that the blocks are found at a consistent rate of time. And nowadays people are throwing massive computational power at solving the puzzle, so unless you have mass amounts of computing power Bitcoin is a non-starter. However, you can mine and find blocks on some of the smaller alt coins. They won't be worth nearly as much as Bitcoin is.
The data being hashed is people's transactions. This is what is meant by "confirmations" when you send or receive Bitcoin. When your transaction is first confirmed, that means it got included into one of these puzzle blocks. Further confirmations mean other people on the peer to peer network agree that it solves the puzzle.
In this way, a consensus is achieved about who owns Bitcoins, and it does not rely on any central authority to accomplish it. That is a very impressive engineering feat!
If you would like to try mining an Alt-Coin, join our RobotSexNickels mining pools. You can also pick up some free coins by commenting on this forum post.