As they put payments in the blocks they find, it's kinda weird...
https://en.bitcoin.it/wiki/Transaction_fees
On the other hand, nobody mining new bitcoins necessarily needs to accept the transactions and include them in the new block being created. The transaction fee is therefore an incentive on the part of the bitcoin user to make sure that a particular transaction will get included into the next block which is generated.
Basically, it's up to the people/pools in determining which TX's are accepted and put into the new blocks as they are found. As you've noticed, those people/pools have been ignoring the low-priority/no-fee ones lately.
http://blockexplorer.com/
Check the 'Transactions' column.
Cheers,
Kermee