Its very easy, they have a .NET passport through msn. They register their email (doesn't matter if it's @yahoo.com, @aol.com, @gmail.com, or @blah.com) and then they are able to sign on to msn messenger with it.
You can get one here:
http://www.passport.net/Consumer/default.asp?lc=1033