I understand that lucky clients that create blocks get some transaction fees and are allowed to mint a few new bitcoins to keep for themselves.
How do clients know how many new bitcoins to mint for themselves when creating a block?
The mining reward is the sum of two parts: Transaction fees and block reward.
The transaction fees are the sum of the transaction fees of the transactions that the miner is trying to validate.
The block reward follows a predetermined schedule: It started with 50 BTC per block and halves every 210,000 blocks. According to the bitcoin.it-FAQ the last block to have a block reward will be block #6,929,999.
The protocol includes a check that will reject blocks which assign more than block reward + transaction fees in the coinbase transactions. Assigning less is valid, however, the difference will be lost.
The block reward schedule is part of the Bitcoin specification. It started out at 50 Bitcoins per block and halves every 210,000 blocks.