The fee system is strange, and not very transparent.  It will probably improve soon.

When you try to spend, your client gathers smaller amounts from your wallet to total more than you are trying to spend, then sends the amount you want to send to the recipient, and the change to a new address in your wallet.  The more transactions it has to gather, the bigger the block will be.  If the block is large, and the transactions are low priority (age increases priority), it will attempt to include a fee.

Other nodes also check incoming transactions, and they may refuse to relay your transaction if it is large (in bytes, not coins) and/or low priority and doesn't include a fee.

Nodes and miners are free to change their own local rules for accepting and relaying transactions, but this isn't currently easy since it involves recompiling the client, or using an alternative client.  Again, this will be improving soon.