How to increase my collaboration "network" as a new faculty? I recently got a tenured (yes, permanent) faculty position in mathematics. During my PhD and postdoc, I collaborated with the same people on some projects, one big and one small, but most of my time was spent on my own, single-authored projects.

This clearly worked, however I now feel like I am missing out. I see all these people at conferences interacting, breaking ground on new knowledge together and having rewarding time working with other people. How do I get to that point?

Not to fall into stereotypes, but I am unfortunately a bit socially awkward, which does not help. I can go out and have fun with other young mathematicians, but walking up to someone and starting talking about a topic of collaboration seems to be out my reach. It never goes further than "I have a question", listening to the answer, and going back to talk with my friend-colleagues.
The best way to start I know of is to quietly pick some small problem somebody else is stuck with (requires no social skills whatsoever, just being reasonably open-minded, flexible, and being willing to listen more than to talk), solve it, and communicate the solution to that person. That will open him up immediately and more often than not a bigger collaborative project will ensue. 

In general, keep in mind that most people are willing to talk about what interests them and are quite reluctant to think of what you are interested in, so learn to work on whatever comes your way rather than only on what you specialize in and let it be the other person who chooses the topic and the direction of the collaborative research. Just go with the flow and enjoy the ride. Note that every time you think of or collaborate on something you haven't tried before it is you, who benefits most by gaining new tools and ideas, and the entry cost is usually not very high: most of the time people are stuck on something that can be easily explained in "mathematical common" and requires just a fresh pair of eyes to figure out. 

In summary, rotate the table: create the situation when other people will seek you to ask questions.