For the most part, Yahoo started out as "personalized start page," like Excite and a few others. They had, and still might have, far more people using any one Yahoo service than Microsoft had using whatever it is they had back then (I'm not even sure they had MSN).
Anyway, all Yahoo had to do was make mail, then their millions of users would automatically get e-mail accounts. From there, it probably spread just the same way as Hotmail.. your-name@yahoo.com, and a little message at the bottom of each e-mail: "get your own email at yahoomail.com"
What's amazing is that it took 6 months for a competitor to come in.