This is a fully correct procedure for determing the fee owed in Bitcoin transaction.
Step 1: Determine the size of your transaction in bytes. It's 12 bytes, plus 204 bytes per input, plus 32 bytes per output. If it's 255 inputs or more, add one byte. If it's 255 outputs or more, add one byte. Likewise if it's 65536 or more inputs or outputs, add another byte. If there's anything even a little bit unusual about the "scripts" involved for any input or output, this formula is not valid. Remember that your transaction usually has at least one more output than is visible; this is because you don't usually have exact change, and the transaction must split at least one of your coins (and may consolidate others) to come back to you.
(NOTE: It has been pointed out that because a key in the input can be 41 rather than 65 bytes, an input may take 180 rather than 204 bytes. The person who pointed this out has not yet provided any way to tell whether an input takes 204 or 180 bytes. Therefore treat the above as an upper bound and 12 bytes, plus 180 bytes per input, plus 32 bytes per output as a lower bound.
Some definite method to tell exactly will be provided as soon as I absolutely know how to tell exactly how long that key is. )
Step 2: Determine your transaction's "priority." The formula is given as priority = sum(input_value_in_base_units * input_age)/size_in_bytes.
But I use input value in millibitcoins instead, to save the bother of dealing with five unnecessary decimal positions.
Your transaction is "free" if all of the following are true.
* it's smaller than 10,000 bytes.
* All the outputs are 0.01 BTC (currently around $8) or larger.
* priority is greater than 576. (note that developers use the number 57600000; it's 576 because I used millibitcoins rather than satoshis above)
Your transaction is also "free" if its priority is higher than the priority of all other transactions in the block except for enough other transactions to make 27,000 bytes but you can't know that when you're figuring out fees. If you don't pay fees the transaction may be indefinitely delayed by higher priority transactions. Anyway, if your transaction did propagate across the network, there will eventually be a block with room to put it into that 27000 bytes. It may not be the next one or the one after that, but it'll happen.
Now, if your transaction qualifies as "free" it will be propagated across the network, though maybe somewhat slower, without fees.
If your transaction is not "free" you had better add a transaction fee. To figure out the transaction fee you need to find the size of your transaction in bytes (see step 1 above), round it up to the next even multiple of a thousand, then multiply the result by 0.1 microbitcoins.
And the final gotcha: if you have to add another input, or more than one other input, in order to cover the transaction fee, then the size of your transaction in bytes has changed, and you must start over and figure out your fee again. And if you get your fee even one satoshi short, then most clients will just drop your transaction on the floor instead of propagating it and you'll have absolutely no benefit from the fee you did add. If your transaction confirms at all it may take days, and the fee will have been a complete waste of your money.