I'm not sure how it works. However, FB algorithms can now detect a "missing" person from a circle. FB algorithms group people into circles, just like IRL. You have your work circle, church circle, sports circle, college circle, et al. From what I've read (again, I'm not exactly 100% sure) is that FB compares friends circles with other of your friend's circles. Then it starts piecing in information on who you might know and how that person is connected to you. That is the main driving algorithm for "People you may know" which works many times freakishly good; other rare times it's out of sync.
That said, using those same algorithms FB can use the exact same data to determine if someone in your circle isn't connected to FB. If enough of your peers use FB, then FB can easily extrapolate a missing person and start building a shadow profile of what that person's likes/dislikes and possible friend connections are. This is also built from data in your friend's phones. This data is fed from contacts, call logs, text history (not actual content, but like to who and how often). and other identifying information. Dislikes and likes can come from what your friends like and dislike as we humans tends to form social circles around common likes and dislikes.
In turn, when you do create a FB profile, and you have several friends on FB, it turns out, you don't need to do much searching because FB already "preloaded" your friends lists in the "People you may know" tab. Something that when sending new friend requests to that possible list, just confirms the algorithm's effectiveness. This way FB already knows you exist and who you are even though you never have a profile with them. It also means FB can easily slap a face to your profile pic because your contacts might upload a picture. That picture may be of you and your friend, but FB's face detection can help (along with other background algorithms) identify you and connect you with the "shadow profile".
In the end, it doesn't matter if you are not officially on Facebook, you already are. Welcome to digital age.
Here is an article on Gizmodo that goes into more detail:
Click Me