Do bitcoin clients automatically add more fee than specified? Sometimes when I'm sending a transaction using json-rpc calls to bitcoind, the client adds more than 0.0001 fee. 0.0001 is the TX fee I specified in the settings.

My understanding is that when the TX size is larger than a certain KB, client automatically adds more  fee. Is this true?

If so, how can I calculate how much fee a transaction will require before I send it?
Yes, an additional fee is added for each 1000 bytes in the transaction.  You can get a rough estimate of the transaction size using this formula:

148*IN + 34*OUT + 10


where IN is the number of inputs and OUT is the number of outputs.  The result can vary by IN bytes since a leading zero is prefixed to keys where the first byte is 0x80-0xFF.  This assumes the transaction is using compressed public keys (bitcoin addresses).

So, for the minimal fee, you need to keep the transaction size under 1000 bytes.  Assuming two outputs (the recipient and change), you can have up to 6 inputs without incurring an additional fee.