"A proof of work is a piece of data which was difficult (costly, time-consuming) to produce so as to satisfy certain requirements. It must be trivial to check whether data satisfies said requirements."
Mining bitcoins involves grouping a bunch of pending transactions together, appending a random number, and computing the hash value until you get one with a lot of zeros at the beginning. Since hashes are essentially random, creating one with a lot of zeros means that you probably tried a lot of random numbers before you got one that resulted in the hash with a lot of zeros. Showing the transaction list, the random number, and the hash with a lot of zeros is "proof" that you did a lot of "work."
Validating transactions is very easy, since you just have to recompute the hash with the one number that "works" and check that it has a lot of zeros.
Mining gets harder and harder (requires more zeros) as more people mine, but if you are successful you get 25 BTC. Verifying transactions stays easy no matter how hard it is to mine, but no Bitcoins are awarded for this.
One point of confusion is that you typically validate as part of mining (as Meni Rosenfeld commented), but you can also validate without mining, which is what most Bitcoin wallets do to be sure they display the correct amount in your wallet.