Proof of stake is a different way to validate transactions based and achieve the distributed consensus.
It is still an algorithm, and the purpose is the same of the proof of work, but the process to reach the goal is quite different.
Proof of stake first idea was suggested on the bitcointalk forum back in 2011, but the first digital currency to use this method was Peercoin in 2012, together with ShadowCash, Nxt, BlackCoin, NuShares/NuBits, Qora and Nav Coin.
Unlike the Proof-of-Work, where the algorithm rewards miners who solve mathematical problems with the goal of validating transactions and creating new blocks, with the proof of stake, the creator of a new block is chosen in a deterministic way, depending on its wealth, also defined as stake.
Also, all the digital currencies are previously created in the beginning, and their number never changes.
This means that in the PoS system there is no block reward, so, the miners take the transaction fees.
This is why, in fact, in this PoS system miners are called forgers, instead.
First POS Proposal: https://bitcointalk.org/index.php?topic=27787.0