David Schwartz's answer is entirely accurate, but all that "bitspeak" might be a little intimidating to the average user. Let me try and put it into more plain language:
The way Bitcoin works is that instead of having one central authority who secures and controls the money supply (like most governments do for their national currencies), this work is spread out all across the network. Most of the heavy lifting for Bitcoin is done by "miners".
Miners collect the transactions on the network (like "Alice pays Karim 10 bitcoins" and "Liam pays Sofia 8.3 bitcoins") into large bundles called blocks. These blocks are strung together into one continuous, authoritative record called the block chain, which doesn't permit any conflicting transactions. This is necessary because without it people would be able to sign the same bitcoins over to two different recipients, like writing cheques for more money than you have in your account. The block chain lets you know for sure exactly which transactions count and can be trusted (so no bad cheques!).
The way Bitcoin makes sure there is only one block chain is by making blocks really hard to produce. So instead of just being able to make blocks at will, miners have to compute a cryptographic hash of the block that meets certain criteria. Bitcoiners refer to this process as "hashing". The only way to find a cryptographic hash that's "good enough to count" is to try computing a whole bunch of them until you get lucky and find one that works. This is the "lottery" that David Schwartz refers to, because miners who successfully create a block are rewarded some bitcoins according to a preset schedule. The difficulty of the criteria for the hash is continually adjusted based on how frequently blocks are appearing, so more competition equals more work needed to find a block. Modern dedicated mining hardware (e.g. ASIC miners) can try trillions of hashes per second, so to be competitive in this race to find hashes miners need specialised hardware, otherwise they will tend to spend more on electricity than they make in the "lottery".
In addition to the hash criteria, a block needs to contain only valid, non-conflicting transactions. So the other main task for miners is to carefully validate all the transactions that go into their blocks, otherwise they won't get any reward for their work!
Because of all this work, when a Bitcoin client signs on to the network it can trust the block chain that was most difficult to produce (since this is evidently the one that was being worked on by the most miners). If there was a "fake" blockchain competing with the real ones (say, where someone pretends that they didn't actually give Sofia those 8.4 bitcoins and they still have them), the fraudster would have to do as much work as the whole rest of the network to make their block chain look as trustworthy. So essentially, the intense work that goes into finding blocks through hashing secures the network against fraud. There is also, of course, some nifty code that figures out how to choose between conflicting transactions; and what to do if two people find valid blocks at the same time.
One last thing: why is it called mining? In the original analogy, people who performed this essential work were compared to gold miners digging the gold out of the ground so that everyone could use it. But in reality, Bitcoin "miners" are just running computer programs on very specialised hardware that automates the process of securing the network. To sum up, this software
- Collects transactions from the network
- Validates them, and doesn't allow conflicting ones
- Puts them into large bundles called blocks
- Computes cryptographic hashes over and over until if finds one "good enough to count"
- Then submits the block to the network, adding it to the block chain and earning a reward in return.
That's mining in a nutshell!