Is it possible to send bitcoins with an attached message with the transaction? If yes how to do it?
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.
Technical details of how to do this are dicussed here. https://bitcoin.stackexchange.com/search?q=encode+message+in+the+block+chain The best way seems to be using the transaction output script.
Blockchain.info has this capabilities in it's wallets. Not sure what other wallets allow it.