A proof of work protocol is a vehicle by which somebody can prove that they have engaged in a significant amount of computational efforts. These protocols often amount to puzzles which, on the 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 that is much less than the time it took to conduct the challenge in the first place.
There are several 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 using a service. The effort 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 were 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 proof of a predetermined answer. These protocols work relative to a challenge string. It has a particular mathematical property about this challenge. In 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 many electricity and CPU cycles to reach this result. It is no surprise, therefore, why the concept of Proof of Stake has arisen.