"Proof of Work" can be very confusing to some. It is the process in which the transactions get entered into the public ledger (blockchain). While mining for bitcoin, your hardware is generating answers to a very complex algorithm. The party that successfully solves the puzzle is rewarded with a block (25 bitcoin at the moment) and receives all of the transaction fees that were posted to that block. Upon finding the block, the party broadcasts the transactions to all other bitcoin clients to synchronize the network.

It would be very difficult to consecutively solve this algorithm with a network that is as large as bitcoin, but even if the network was much smaller, the algorithms auto-adjust their difficulty to account for how much hashing power is on the network. This keeps the mining process much like a random lottery (unless someone has control of more than half of the entire network). Proof of Work is much like a system of checks and balances. The random generation keeps the playing field level and creates an honest ledger of every transaction.