Trial and error + filtering other people's opinions.
Many employees kept internal blogs on things they were working on (including CEO Chambers). Employees also had keywords for things they liked to do or were good at (C#, starcraft, hiking, investing, etc would be someone's keywords). There were also a lot of mailing lists to search to find people who liked to do things together (pythonistas, bxb-cycling, bikers, etc)
Other than that there was simply reputation (this is the 'filtering other people's opinions' bit). J.C., for instance, was known around the office as being a hilarious guy and just great to talk to. S.D. knew everything in the world about firewalls. D.C. was a great artist, yada yada...
I guess it really depends on how your company is set up and how comfortable you are approaching people.
This is just bizarre to me. I'm not the worlds most extroverted person, but creating and maintaining social relationships at work has been the single most powerful thing I have ever done to: Learn new things, advance my career, form mentoring relationships (both as a mentor or mentee), try new foods (one of the great joys in my life)etc....
If you aren't getting anything valuable from lunch with other people, you are doing it wrong.