A proof of work protocol is a vehicle by which somebody can prove to you that they have engaged in a significant amount of computational efforts. These protocols often amount to puzzles which on one hand can be challenging to solve and require some serious computational efforts, and on the other hand, can be easily verified in a time which is much less than the time it took to conduct the challenge in the first place.
There are a number of applications for such protocols, and one such example would be its use in the bitcoin blockchain. These types of proof of work schemes have been proposed before for other applications. For instance, PoW schemes have been proposed for doing things like deterring denial-of-service attacks, or DoS attacks. Here the idea is that the requester of a particular service would have to solve a very particular computational problem before being allowed to use a service. The effort which is to be exerted is expected to act as an effective way to throttle the requester. The responder can easily check if the requester carried out the requisite work, and only if that work was carried out the responder would grant access.
When a new block is produced, it needs to be appended to the blockchain, and all of the miners try to mine it. So what do we mean by mining a block? It means when a block arrives we hash all of the transactions in the block and we get a hash of all those transactions. On receiving this hash, miners start to work on deriving a proof of a predetermined answer. These protocols work relative to a challenge string. It has a very specific mathematical property in relation to this challenge. In the case of Bitcoin, when a miner comes up with a correct proof, the block is added to the blockchain and the other network nodes are notified of the same.
Unfortunately, this process is expensive and requires a lot of electricity and CPU cycles to reach this result. It is no surprise, therefore, why the concept of Proof of Stake has arisen.