Obviously locality makes it a lot easier but even then, there had to be a point where you had 5 users and nobody else. How do you get past that?
First, I posted the site on a local subreddit, which got us up to about 20 users. We started telling friends and friends-of-friends, and my partner ponied up about $800 to run some radio ads. Fun fact: radio stations will whip up an ad for you as part of their fee. It was pretty fun hearing that on the radio.
After that first hundred users or so, we started sending press releases out to anyone we thought might care. This was much easier being local, and easier still because my wife is a writer with some experience being on the receiving end of PR press releases, and she wrote it up for us.
We were lucky enough to be featured in the local paper of note, got an interview on local radio, and a week later we were up to about 1000 users. The rest we've picked up more or less organically through word-of-mouth and/or google.
Edit: This was back in October. I wrote this mostly about the technical details, but it has some experiential stuff too: http://adambard.com/blog/my-experiences-deploying-a-small-cl...
Pre-registrations for online dating are different than with other kind of consumer apps. Daters eventually stop being single. So pre-registrations are most useful if they are for a short period of time - no more than, say, eight weeks. This ensures that your profiles are accurate (single people are actually single and will become active users once you launch.)