Ah I didn't realize someone else has to verify a transaction. So whenever a new block is found or someone pays for something using bitcoins, a third party has to verify the transaction for it to be registered in the block chain? And for this to be done requires a transaction fee to compensate the 3rd parties time?
Bitcoin is a voluntary system. It is not "required" that you include a fee. You are welcome to attempt to broadcast a transaction with no fee (some wallets prevent this under certain circumstances, others will allow you to do so regardless of the circumstances).
However, peers are not "required" to relay your transaction. They are welcome to refuse to relay it for any reason they like. Most peers will be running the "reference client" called Bitcoin-Qt. In that case they will relay most all transactions, but if the transaction appears "spammy" or like it could potentially be part of a denial-of-service attack on the network, then they may refuse to relay the transaction if it doesn't include a sufficient fee.
Additionally, miners are not "required" to include your transaction in a block. They are welcome to refuse to include it if they feel they can increase their profits by including some other transaction that has a fee instead of your "free" transaction.
This all being said, most all "free" transactions where all outputs are greater than 0.01 BTC and the total size of the transaction is less than 10 kilobytes, will be relayed and will eventually be included in a block by a miner. Miners see a long term benefit to maintaining a system that is cheap and easy to use. The miners are currently subsidized by the minting of new bitcoins, and they get enough revenue from that subsidy that they are generally willing to include a reasonable number of "free" transactions in each block they mine.
Every node that relays the transaction "verifies" it. The miners register it in a block to "confirm" it. This process requires both time, and more importantly energy (in the form of the electricity required to perform the "proof-of-work").
Since you could theoretically broad cast 2 different transactions each using the exact same bitcoins, sending each of the 2 different transactions to a different sub-set of the current bitcoin network, this "confirmation" process of adding one of those transactions to the blockchain is how the bitcoin network comes to a consensus on which of the two transactions is legitimate and which can be disregarded as invalid.