Bitcoin PoW in a nutshell:
PoW: the work demanded for miners to win the race.
Something hard to produce but easy for everyone to verify.
For a new block to be added to the blockchain a certain computational problem must be solved.
It consists on findind p on the expression h(p) = d. The value of d is known beforehand.
Once it's not possible to obtain h(p) from d, a lot of trial and error is required to find the correct p.
Therefore, PoW is the proof that a miner indeed made an effort to satisfy a certain condition.
Bitcoin uses the Hashcash proof of work system.
Getting more technical...
PoW is a piece of data difficult to produce but easy for others to verify it satisfies certain requirements.
Producing a proof of work can be a random process with low probability so that a lot of trial and error
is required on average before a valid proof of work is generated.
Guessing the string digest beginning with 40 zeros generated by a hash function.
If you have a good cryptographic hash function, the only way is to try a lot of possibilities.
How? Brute force. Trial and error.
Steps on average to take the right guess: 2^40 = 1,099,511,627,776 (approximately 1 trillion steps).
Proof of work is an economic measure to deter denial of service attacks (and other service abuses such as spam)
on a network by requiring some work from the service requester. The work is usually processing time by a computer.
Hence, an entity has to pay the price with CPU cycles (electricity).
The work must be moderatelly hard (but feasible) on the requester.
It also must be easy to check for the service provider.
On the Bitcoin network every node can check if a miner actually solved the problem and then valid this new block.
Hashcash proofs of work are used in Bitcoin for block generation.
Miners must complete a pow that covers all the data in the block.
Bitcoin blocks are added to the blockchain on average every 10 minutes because this is the time that miners take on average to solve the problem.
Raising the difficulty: adding just one zero = double the difficulty!
Likewise, every time you remove a 0 you reduce the computational power to about half.
The difficulty of this work is adjusted so as to limit the rate at which new blocks can be generated by the network to one every 10 minutes.
Just take the string found, hash it and then check if it's equal to the digest expected.
Once a miner wins the race he/she broadcasts to the network the new block.
Every node in the network check that is a valid block and add it to their copy of blockchain.
Proof of work example
Base string we're going to work: "Hello, world!"
Our target is to find a variation of it that the SHA-256 hash function hashes to a value beginning with '0000'.
We vary this string by adding an integer value to the end called a nonce and incrementing it each time.
Finding the right digest that begins with '0000' takes us 4251 steps.
"Hello, world!0" => 1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64
"Hello, world!1" => e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8
"Hello, world!2" => ae37343a357a8297591625e7134cbea22f5928be8ca2a32aa475cf05fd4266b7
"Hello, world!4248" => 6e110d98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965
"Hello, world!4249" => c004190b822f1669cac8dc37e761cb73652e7832fb814565702245cf26ebb9e6
"Hello, world!4250" => 0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9
See this application that demonstrates this concept.
Hash functions (Wikipedia): here
Proof of work system (Wikipedia): here
Proof of work (Bitcoin wiki): here
Hashcash (Bitcoin wiki): here
Target (Bitcoin wiki): here