To have a useful payment system, if I have some asset the system supports, I have to be able to send it to Alice if she is a user of that system. And I also have to be able to send it to Bob if he is a user of that system. But if I can do both of these things, the system stops being useful. So, for bitcoin, somehow sending bitcoins to Alice must prevent me from sending them to Bob and vice versa.
Traditionally, this would be accomplished by a central authority. For example, my bank can process checks in the order it receives them, approving them if I have a sufficient balance and deducting that amount from my balance. The bank can prevent me from sending the same money in two places. But bitcoin has no central authority.
Bitcoin's solution has several pieces.
First, it groups transactions into blocks. Second, it chains blocks into a blockchain.
Third, it has rules for what is or is not a valid blockchain. For example, a chain that includes two conflicting transactions is not valid. So, in my example, either a blockchain can include my payment to Alice or my payment to Bob, but not both. This works because all transaction and state information is public, so nobody would ever accept any blockchain with conflicting transactions unless they chose to foolishly harm themselves.
But we still have one problem left -- how do we ever get everyone to agree on which blockchain is valid if there's one that includes the payment to Alice and one that includes the payment to Bob? That's where proof of work (mining) comes in.
It consists of two steps:
1) To add a block to the blockchain, you must do a very large amount of computational work.
2) You will be rewarded with bitcoins for doing this large amount of work, but only if the blockchain that contains the block you added becomes the one everyone agrees on.
And lastly, one more rule: We agree on that valid blockchain that has required the most computing power to generate.
Under reasonable conditions, this assures that everyone will eventually agree which of the two transactions is valid. Miners are incentivized to build on the longest, valid block chain they know of, because that gives them the best chance of being rewarded. Thus longer chains will tend to get longer and shorter chains will tend to be ignored. Eventually, one chain will be so much longer than every other chain that we everyone is mining on top of it and nobody is mining on top of the other and there is no chance the shorter chain will ever be longer.
Once that happens, and the longer chain contains one of my two transactions sufficiently deep in the chain, we can all agree which way my bitcoins go. And no central authority is needed.