What method does My Wallet use to encode messages in the blockchain? 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...


and by Gavin Andresen here.


  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.