Proof of Work
Proof of work is a consensus algorithm.
Proof of work is a method used to determine who has the right to speak on a P2P (Peer to Peer) network. In classic P2P networks, each IP address or process has the right to speak. In the Bitcoin world, the right to speak is granted based on the CPU power of a node or group of nodes.
The right to speak, which in Bitcoin is the right to confirm a block on the Bitcoin blockchain, is given to the first node or group of nodes to solve a problem requiring a great amount of computational power (i.e. finding a hash that meets a specific condition).
On the Bitcoin network, the ability to introduce false information would require more than half of the CPU power of the entire network. As more blocks are confirmed, a retroactive modification becomes exponentially difficult, hence it can be said to be virtually impossible to mount an attack on the Bitcoin network in this manner.
More generally, there is the concept of a "proof of resource," of which the proof of work (PoW) is one form (referring to CPU resources).
With altcoins, proof of stake (PoS) is often used. In this model, participants' say is based upon their stake, which is basically similar to their say being based upon the amount of coins they own. Unlike with PoW, with PoS there is less electricity used. However, in most cases PoS is not used on its own, and is used in conjunction with PoW or another setup.