Well, typically they did it the same as everyone else tries to:
- Provide a good feature set
- Get known through blogs, sites
- Get known through word of mouth (facebook is like the zombies, more makes more)
- Draw people with advertising
- Respond to the users requests and suggestions, nothing like seeing "your" feature to make someone think fondly of the site.
- Run "tell a friend" competitions or other viral drives ... getting this right is somewhere between an art form and pure luck.
- Get linked from larger more established sites to drive traffic
- Have a bunch of well known people talk about the site.
- Make it easier to use than everyone elses sites.
- Make it fast and responsive. Google raises you higher if your faster, plus all the research says a minor tweak can make a massive difference (listen to BayCHI and Interviews with Innovators for details)
- Find a vertical that they know well. If you have specific, domain knowledge then use it, make it publically accessible and enable other to untilise it as a part of their solution.
- Find a vertical that they have a key point of difference in.
- Have an API, these days its pretty much manditory if your a service or site.
- Have a technical advantage. You own an algorithm or special piece of the puzzle, other pay you to "do your thing".
- Find a vertical that isn't being owned by a good player. (Google had a new spin on search which everyone else believed was a mature / closed market)
... The companies you listed were just part of the "early wave" on the net and are now the "long established players". The next wave is coming through, there are a lot more of them and they are a lot better at it because there are sites like this one to let everyone know how to solve all the problems the earlier wave had to learn ...
So, most of what I said is now old school and if you can find a new method that doesn't involve spamming people with twitter messages no one reads ... let me know cos I would love to try it out.