The following advice is from a book I read some time ago, but the advice stuck with me because it made such sense. I am pretty good socially, but I had never thought about what I did that made me so good at it. Here goes.
Small talk is certainly a starter. But it has to be the right small talk. Walking up to someone and talking about yourself will certainly push people away. But asking about them–how their day/week/year/ is going, etc.–will usually get a positive response. People usually like to talk about themselves, and even if they don’t, it will usually be taken as a sign of sincere interest in them, and most people like that. Then, eventually, they will be curious about you (such is human nature). Pretty soon, it’s them asking you “So, how’re you doing?” And then you get to talk for a bit. Eventually, you might start exchanging contact info.
Or, you might not. It might just be small talk, which is okay. You can’t be friends with everyone. Sometimes, friendships start out of a combination of small talk and circumstance. I’m friends with my office mate (a fellow doctoral student but in a different program) probably because of circumstance more than anything, because if he were assigned to a different office, we might not have had a chance to spend much time together. He’s just starting course work, and I’m ABD. But being in the same office, get to interact with one another. I’m glad circumstance put us together; he’s a great guy and a good friend.
Bottom line: You must show interest in other people before you can start a friendship (99 times out of 100; I am a statistician, after all, so I rarely talk in absolute terms). Once you get outside of yourself, you’ll find other people who are interested in you also.