Let us start by what they have in common: they are both algorithms for reaching consensus on the blockchain.
Without going into too much details, we need consensus because anyone can create a block; while we only want an unique chain, so we want a way to decide which block we should trust.
Proof of work has the nice property that you can use Bayes' Theorem and the laws of Thermodynamics to prove that a given block has indeed required a certain amount of work to be mined. That way, users can simply pick the longest valid chain with the highest amount of work as the correct chain.
But this implies that Proof of Work is extremely inefficient in term of energy, and therefore also very expensive; which incentivize miners to centralize the hashing power -- obviously not desirable for a network whose goal is to minimize the need to trust third parties.
Proof of Stake isn't about mining, it's about validating. In effect blocks still need to be created by someone, and who gets to create the next block depends on the specific Proof of Stake algorithm, but the selection process must have some kind of randomness, or at least distribute voting shares properly (otherwise we revert to a centralized system).
In PoS, each validator owns some stake in the network, ether in the case of Ethereum, that they bond. Bonding stake means you deposit some money into the network, and in some sense use it as a collateral to vouch for a block.
In PoW you know a chain is valid because lots of work is behind it, while in PoS you trust the chain with the highest collateral.
There are important differences between the various Proof of Stake algorithms that are being developed. This question is about PoW vs. PoS so I'm keeping the answer very general.
Ethereum is going to use Casper, where the stake of malicious validators is going to get (partially) slashed, for example if they sign two (competing) blocks with too high a probability.
Best Answer
Proof of Work like proposed by Satoshi doesn't solve the Two Generals Problem or the more generic Byzantine Generals Problem. It's a probabilistic solution to the Byzantine Generals Problem, which means the confidence that a consensus is reached is growing with every block added to the chain, but it never reaches 100%.
https://medium.com/loom-network/understanding-blockchain-fundamentals-part-1-byzantine-fault-tolerance-245f46fe8419
Practical Byzantine Fault Tolerance (PBFT) for instance will guarantee consistency (no forks -> 100% finality) in a system with 3*k+1 nodes only if the number of traitors does not exceed k. Hence, you‘ll need at least 2*k+1 votes for a block. The reason you need 2*k+1 is that for every number smaller than that, you can not be sure that traitors are not in majority for this subset. See Liskov/Castro Paper on PBFT for details.