The payment protocol (see BIP 70-72) will support attaching messages to transactions.
Note that these messages do not end up in the blockchain, which is the right way to do it, as they are private information between sender and receiver - no need to make the entire world replicate it.
