From what I heard, both contacts must invite each other, after which they automatically become friends.
However, I added my test account on one of my others, and after a few minutes, the test account contact list showed "you have 1 invitation", so I'm not sure if the method differs in Messenger versions (I tested it with both accounts using WLM 2011)...
