How does blockchain.info associate a message with an address?
This is known as "tags", and it is 'blockchain.info' specific. You can use any web page, or bitcointalk.org user profile or bitcoin-otc Id as link. Your link page should contain your address.

http://blockchain.info/tags