I was spooked out by Facebook when I signed up (being forced by another site that required a Facebook login) and had it immediately present me with a long list of people I might know, and indeed knew at least a hundred of them. How did they know considering I never gave them any history? Scary.
When new users sign up for Facebook, the site encourages them to send it their contact lists from Gmail, Hotmail, etc. in order to search for their friends on Facebook. Even if you chose not to do this, probably there were a few of your friends who had your email address in one of their contact lists. I bet it saves that information so when you signed on, it showed you those names.
In addition, the site cross-references people's mutual contacts, under the assumption that if you're friends with Adam and Bob and both of them know Chris and Dave, then you likely know Chris and Dave as well.