A fee is added per kilobyte of data. That means 1000 bytes or 1024? Wikipedia says kB = 1000 bytes and KB = 1024 bytes.

Which one are we using for Bitcoin?
According to the Bitcoin.it-wiki page on Transaction fees are dependent on multiples of 1,000 bytes  (rounded up).

The above page cites Gavin Andresen's post on 0.8.2 Release notes:


  The default fee for low-priority transactions is lowered from 0.0005 BTC
  (for each 1,000 bytes in the transaction; an average transaction is
  about 500 bytes) to 0.0001 BTC. [emphasis mine]