What kind of protocol does My Wallet use?
Messages are stored in a database at blockchain.info (so that text should probably be changed). For a while it did use the blockchain for storing messages but this was changed after concerns from a few of the core developers.
Concerns were expressed by Matt Corallo here
Oh god, thats awful...that is quite possibly the worst way to implement messages in terms of network load...
Yes, please don't create lots of unspendable scriptPubKeys. There are more prunable ways of embedding messages into transactions. And there are even better ways of associating messages with transactions, so only people involved with the transaction can read the message (if that's desired).
Here is the message that implementation was changed back to using a centralized database.
Since a few developers have expressed concern I've changed the notes back to the centralised database for now. I still think there are many use cases where you might want to contact the owner of an address without needing to know an email etc, a decentralised way to do this would be great.