The client checks the size of the transaction in bytes. The size depends on the numbers of inputs and outputs, and is roughly:
148 * number_of_inputs + 34 * number_of_outputs + 10
If this size is less than 10,000 bytes and the transaction's priority was high enough to qualify as free, then the transaction still qualifies as free, otherwise a fee is required. The fee is charged per 1000 bytes or part thereof. The amount charged per 1000 bytes defaults to 0.0005 BTC
Full article at
http://bitcoinfees.com