Philip Kaplan, founder of quite a few companies that you've heard of (FuckedCompany, AdBrite, and others), shares some advice about how to get those initial users:
The best sites seem to take of magically by themselves. Truth is, every site needs a little kickstart to get to its first 10,000 to 100,000 users. Consider this a list of kickstarters. But keep in mind the saying, “nothing kills a bad product faster than good marketing.” You have been warned.
The techniques covered include starting controversies, using viral tricks, affiliate programs, SEO, press, celebrity endorsements, business development deals, and offline events. None of the tips are covered in too much depth, but Philip does give examples (some based on his own experience) of how each of them has worked in practice, and so this article is certainly worth a good read.