<speculation>
He had her wallet. He searched and found her on facebook. That's surely enough for FB to think they know each other.
Not sure - I had a business contact come up the other day. We have only been in contact via my work email account that is not linked to Facebook. Lord knows what bits of data Facebook has access to and is able to stitch together to make the bigger picture.
If you install the facebook app on android, fb can access your address book. So if any one who knows you has multiple email address listed for you under one contact, then facebook could have associated all your email addresses with your account. Then as soon as your contact added you to his address book, FB could make the connection.
Apparently it's a huge problem with AA - alcoholics anonymous. You only exchange first name, and have each others phone number so you can reach out if you need support. FB app immediately takes that phone number, and suggests you might know each other. Instead of being anonymous, you know more about each other than you would have known about most of your friends, pre-facebook.
<- sad but true.
