[leashless]

Bigger computers equals faster search, which we could explain to non techies as buying more lottery tickets. I try never to explain mining to a general audience. It's too low level for a clean semantic mapping between what they want to know about, and how it all really works.

[count_zero]

Maybe this analogy would work:

Imaging a million haystacks with a million different keys scattered within them. There is a lock which only one of those keys can open; it is difficult to find the key, but when you do, anyone can easily verify it is correct by turning it in the lock. Once a key has been found, a new lock is created and the process starts again.

The more robots (mining power) you have to search for the key, the more likely it is that you will find it before competing machines do.

[rocqua]

Besides explaining how we are looking for a nonce, I find it both difficult as well as elucidating to explain how whomever mined a block is rewarded.

The main point of block-chain is decentralization. It is thus important to emphasize that there isn't a central authority that rewards the mining of a block, but instead that the miner includes his reward in the block. It is also important (though less relevant) that the challenge of mining a block is a mathematical result of the last block. It too arises without a central authority.

Moving to even less relevant and yet interesting thing is that not all miners need be mining the same block. This is already the case for the 'reward' they are mining, but miners are free to exclude a transaction from their mining attempts. This then begets the matter of fees as a secondary incentive for mining besides the block reward.