People often claim that with Bitcoin "you can send money between any two points on earth for free". While that is true in some cases, sometimes a transaction fee is required. The fee, when it is required, is usually worth a few dollars.
The fees go to the miners to incentivise them to keep mining, which in turn keeps the Bitcoin network secure. They already get a reward of 12.5 XBT for each block they mine, but this reward halves every 4 years. The plan is that as the block reward diminishes over the time, it will be replaced by transaction fees.
So what decides when you have to pay, and how much?
Well, like everything else in Bitcoin, the fee structure is built into the network rules, which are defined as "what the reference client does". When you attempt to send coins using bitcoin core (the current reference client), it goes through the following steps:
1. Pick which coins to spend
The client has to decide which of your coins to use to make up the payment amount. Each time you receive a payment, the payment goes into your wallet and stays there until you spend it.
If you receive a payment of 2 XBT and another of 3 XBT, you'll have 2 new amounts in your wallet, of 2 XBT and 3 XBT. They don't "merge" into a single 5 XBT coin. Over time you'll build up a collection of differently sized amounts in your wallet, and the client needs to decide which ones make the best fit for the amount you're trying to spend.
These amounts are known as the "inputs" of your new transaction, and the amounts you are sending (including any change that gets sent back to your own wallet) are known as the "outputs".
2. Discourage "dust" spam
If any of the outputs (including any change) of your transaction are less than 0.01 XBT, then a fee of 0.0001 XBT is required. The coin selection algorithm is careful to avoid selecting coins that result in a change amount of less than 0.01 XBT if at all possible.
3. Prioritize old and high-value coins
If the coins you're spending are too small or too new then your transaction won't qualify as free. Each transaction is assigned a priority, determined by the age, size, and number of its inputs.
Specifically, for each input, the client calculates the value of the input in XBT multiplied by the age of the input in blocks. It sums these products over all inputs and divides the total by the size of the transaction in bytes. If this gives a number less than 0.576 then the transaction requires a fee. This means that you can include lots of very small, and/or very new inputs in a transaction and have it require no fees at all so long as you include a large old input along with them; it is the average value-times-age that matters.
If step 3 caused a transaction to require a fee when it was originally sent, it's possible that as time passes, and new blocks are found, the transaction's inputs will age, its priority will increase, and as a result step 3 may no longer cause it to require a fee.
4. Charge per kilobyte
Finally, 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 step 3 found that 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.0001 XBT, but can be increased in the Settings>Options>Main tab of the client. If you set the "fee per kB" to less than 0.0001 XBT in that dialog then a value of 0.0001 XBT will be used. When it applies, this fee per kB replaces any fee from step 2, rather than adding to it.
All these rules are visible in the reference client's source code. See CTransaction::GetMinFee() in src/main.cpp, AllowFree() in src/main.h, and CWallet::CreateTransaction() in src/wallet.cpp.
1. When Too Much is Not Enough...
Suppose you have only two outputs in your wallet, worth 1 XBT and 2 XBT. You want to buy something for 2.999 XBT. The coin selection code has no choice; it has to select both coins to get a big enough total to make the transaction. That means the change will be 0.001 XBT, which triggers the 0.0001 XBT fee for having an output that's less than 0.01 XBT. As a result your transaction will fail, because the amount you're sending plus the fee is more than you have.
What this means is that there's no way of spending 2.999 XBT when you have 3 XBT. You could send the full 3 XBT to the vendor without a fee (assuming the outputs are sufficiently old to satisfy step 3), but some vendors ask you to send the exact amount they specify.
2. The Big Dice Winner
Once, someone got lucky and turned 0.02 XBT into 1280 XBT on a 64000x payout bet on a bitcoin 'dice' game! When the site paid out the winnings they didn't have a single 1280 XBT input lying around in their wallet. Instead what they had was a whole bunch of various sized outputs from other players' losing bets, as well as a lot of change from paying other winners.
The transaction the site created to pay the winner of this jackpot used so many inputs that it ended up being 51,203 bytes long. Being over 10000 bytes, this required a fee of 0.0005 XBT per 1000 bytes or part thereof (prior to being changed to 0.0001, the fee used to be 0.0005), so the required fee was 52 * 0.0005 = 0.026 XBT. That's more than the player bet in the first place. Who says Bitcoin transactions are free!
Of course, this is still less than you would pay in fees if you used PayPal to transfer $40,000.
Note that the dice game actually included a fee of 0.0286 XBT, which is more than is required. That's probably because they don't use the standard satoshi client to create their transactions, and the client they used got it slightly wrong.
3. Pushing the Limit
This transaction just barely qualified as being free. It's 9999 bytes long, which is the biggest a transaction can be without requiring a fee. Notice also that all but one of the inputs are only 10 nXBT (0.00000001 XBT); the single large input that was included with them was big enough to bring its priority up enough to make it free.
Are "required" fees really required?
Incidentally, the concept of "required fee" isn't strictly enforced. Some miners don't follow the rules about what fees are required, and will include a transaction in their blocks even if it doesn't follow the fee rules. Using the "raw transactions" interface of the reference client it's possible to create transactions with less than the required amount of fee. Such transactions may eventually be included in a block by a maverick miner who doesn't enforce the fee rules, although this could take 24 hours or even much longer.
So it's all pretty complex, but hopefully this gives you a better understanding of how and why the client decides when and how much to charge you.