Graduate students talk to other researchers, other than their formal advisors, all the time, whether at their home institution or at conferences. They get help on specific tasks, ask for input on their current work, or even to discuss research ideas.
However, as a graduate student, forming a significant collaboration with another researcher without checking in with his/her formal research advisor can be seen as "going over the advisor's head". Of course there is no hard and fast rule about this, and exceptions abound I'm sure, but then the student runs the risk of arousing the ire of his advisor, especially if the researcher is not a close associate of the advisor. Sometimes, this is because there may be "bad blood" between the advisor and the researcher, unbeknownst to the student. Also, if there is indeed politics between the two, the other researcher may be less prone to responding to the student, as the student is essentially seen as "belonging" to his or her advisor.
Is this still the case as a postdoctoral researcher? Does one gain more independence as a postdoc? If there are political differences between your hiring faculty Prof. X and potential collaborator Dr. Y, will Dr. Y be more likely to shy away from collaborating with you just because you're associated with Prof. X?
Talk to your boss in general terms at first. Then you'll get a feeling for whether a "go for it" approach will go down well locally or not. You may have a good idea of whether you're working with a natural collaborator or not, but an early discussion is still worthwhile because they can warn you in general terms about rivalries/conflicts of interest etc. Try your hardest to keep your boss in the loop at all times. Of course this isn't always possible when you meet people at conferences.
Don't make promises you don't have the authority to keep -- so discuss possibilities rather than actually inviting someone until you can clear it. It might not be just your boss but politics/policies that you have to deal with. Money is always a good get-out: If you don't hold the budget yourself, everyone knows you can't just spend it without authorisation.