http://www.bitcoin.org/wiki/doku.php?id=transaction_fee This has information on the current fee schedule that the standard client uses.
You are free to charge more or less, but right now since no one is sending more or less it wouldn't matter. Likewise you could modify your client to send a transaction that requires a fee with no fee or less fee, but no one will block it unless they have modified their client.
I wonder is there a way to view transactions that are waiting because they do not have the associated fee? I realize there are probably none, but eventually that data would be useful for determining a custom fee schedule.