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.