Hm, I'm surprised this has never gotten a more comprehensive answer.
Brand-new sites start out in "private beta", where the reputation requirement for voting is 1 (i.e. everyone may vote). These votes count the same as any other vote for the purposes of rep increases (or decreases). (DMA's answer discusses this.)
Even after the short private beta period, there is no reputation requirement for askers to select accepted answers, which carry a +15 rep reward. This means that even if a new user answered a question from another new user, acceptances could get sites off the ground. (Geoff's answer mentions this.)
Users who are new to a given site—even a brand-new site—but have some experience with other network sites usually get a 100-rep bonus right off the bat, in recognition of their understanding of Stack Exchange mechanics. This bonus is enough to allow those users to vote, and even offer small bounties. (Robert's answer has more about this.)
Shortly after a site is started, it gets a set of moderators, chosen from the community. Those moderators, as well as a select group of Stack Exchange employees, have the ability to cast votes (as well as all other reputation-based privileges) ex officio, regardless of their actual reputation on the site.
In the years after this question was asked, a new feature was introduced: suggested edits. Users of any reputation level may suggest edits, and for users without the "edit anywhere" privilege, the first 1000 suggested edits that are approved result in a +2 rep reward. Even on a site with the "full" reputation level for editing, it is theoretically possible to earn the editing privilege by doing nothing other than suggesting edits.
Finally, just for historical interest, there was a time years ago when the system would create rep "out of thin air" to add to bounties. This is no longer done, but could have accelerated the growth of some sites in the past.