How do Bitcoin clients know how many new bitcoins to mint when creating a block? 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.