Proof of Work
First, within the realms of Bitcoin and cryptocurrencies, both Proof of Work and Proof of Stake are used as a part of consensus algorithms.
Algorithm is simply a set or steps that computers execute. For example, when a person cooks, the recipe is a sort of an algorithm. The same is with computers. Computers execute commands and algorithms define what those commands are and in what order they need to be executed.
What about consensus? As you are well aware, Bitcoin and other cryptocurrencies do not have a centralized server or central authority. Rather, Bitcoin network is made up by numerous computers running the Bitcoin software. To put simply, consensus is the way how these computers running on the Bitcoin network agree on transactions.
The idea of Proof of Work is very simple. Imagine that there is a certain service and a user of this service. In order for the user to use the service, she must present something that requires certain work. However, this work has one peculiarity - it’s very easy to verify if the work was really performed or not. This is how Proof of Work algorithms work and that’s what exactly what Bitcoin miners do. Within the context of Bitcoin, the Proof of Work means that you have done certain amount of calculations (and thus consumed some energy). Anyone involved in the Bitcoin network can easily verify that you have indeed performed the work.
The Proof of Work is a wonderful invention but is has one serious drawback - it consumes a lot of energy and thus it has certain impact on our environment.
Proof of Stake
An alternative solution is Proof of Stake. Proof of Stake is a bit more difficult to grasp because it’s a bit more abstract.
One thing to note is that Proof of Work is not limited to Bitcoin and cryptocurrencies. It has some other use cases, for example to fight spam (though it must be noted that this use case has not taken off). On the other hand, Proof of Stake is something used within the cryptocurrencies and blockchain realms.
In those systems that use Proof of Stake, the owner of a new block in the blockchain is chosen based on some random combination of wealth and age. However, this is a very simplistic view. For example, if only wealth were used, then this would cause undesirable centralization as those with the biggest balance would be chosen as block owners almost all the time. It must be noted that Proof of Stake algorithm has many problems and these problems have not been fully solved. The Proof of Stake has a big advantage of not consuming energy but the weaknesses are also considerable. So unless these problems are solved, the Proof of Work approach is more robust and viable.