blockchain.info allows you to attach messages to a tx in their database, but you can also imbed messages in the blockchain itself.