The ways characters relate to one another is a fundamental part of the roleplaying experience in my mind, at least as important as a character's relation to the world around them.
But there are a few schools of thought about character's relations to one another. Should you apply specific formulae to the dynamic of players interacting with one another through their characters? Should you let players evolve the dynamic for themselves?
It's like a lot of things, different groups will work better with different answers to the question.
At one end of the spectrum there is the tradition of Australian Freeforming, purely about intercharacter connections. At the other end of the spectrum you get traditional tabletop play, where characters are defined by what they can do to the world around them (and anything else is purely resolved by unwritten social interactions and negotiation between the players).
I'll go through the spectrum the way I understand it...
Purely driven by interactions between characters (Australian Freeforming)
Predominantly driven by interactions between characters with some story impetus (Jeepform, Nicotine Girls (from what I understand about it)...)
Driven by a balance of character interactions and story impetus (Many current Indy Games, Panty Explosion, Dogs in the Vineyard, White Wolf's Minds Eye Theater...)
Predominantly driven by story impetus with some focus on character abilities (Many early Indy Games, 3:16, Zero, ...)
Predominantly driven by individual abilities with some focus on story impetus (White Wolf Storyteller System, Spycraft/Modern d20 System...)
Purely driven by individual character abilities reacting to the outside world (D&D, Palladium Games, most other "mainstream" games...)
There are plenty of games I haven't mentioned above, I've specifically only included the big names that are easily recognizable, or ones with which I'm really quite familiar. The games above can vary their place on the scale up or down by a point depending on the GM and group playing, but the placement given is according to the way I understand them to have been designed.
But how do these games achieve their character interaction?
Looking at a simple version, I'll pick White Wolf's Storyteller system: "Werewolf" characters are typically grouped into a pack, one player takes the role of the pack alpha and other characters take on specific roles to define their place in the scheme of things compared to one another. "Sabbat Vampire" or "Kindred of the East" are perhaps the most advanced level of character interaction where specific degrees of bond between characters are monitored on the character sheet. Such a bond fluctuates through play as characters share blood, or spiritual energies with one another. In some ways these games may seem a bit contrived or forced, but this has been written into the source material as an instinctive aspect of the characters that the higher mind might rebel against (but has to accept none-the-less).
Moving up the scale, Minds Eye Theater (MET) plays up the aspect of social interplay with boons and oaths offered between players and major social ramifications applied for the breaking of these oaths. Each of the sub-games within the MET series has players who specifically take on the role of monitoring the flow of social interaction. Naturally, such a game requires a high number of players for these roles to become effective. The social interaction bestows an order on the group within the context of the game, and provides additional roles for players to take on when they aren't specifically excited by the role of "combat monster", "mystic" or "scholar". It could even be argued that these games are more easily reigned in and even self regulated, because there are players within the setting who aim to keep the peace rather than just GMs who try to railroad events.
At the highest levels, social interaction is applied in the manner of the Australian Freeform. Players are nothing beyond their connections to one another. Everyone wants at least one thing from the situation, and everyone wants at least one other person not to achieve their goals. Players don't necessarily know who to trust (because some people will be able to help their agendas, others will be actively hindering them, and many will be too busy pursuing their own unrelated goals). Players don't know the best way to achieve their goals, but they know that they'll have to keep things on the lowdown, in case their enemies gather in opposition. Some games apply basic rules for working together, others apply basic attributes to their characters for "just in case" players want their characters to go head to head. But the whole aim of these games is to get players to talk to one another, plot and scheme. It's what the set up does well, and for twenty years the formula hasn't changed much.
Players are divided into small groups with a common background or a common goal. Each individual within the group has a second goal that links them with members of other subgroups. Each individual is aware of one or more enemies existing in other groups, and they are aware of shadowy events that they must try to stop. Over the course of the freeform, events will be set into motion through the common will of the players, or at specifically designated periods by the GMs if things don't seem to be moving well otherwise. Gradually the players gather interest in one or two core storylines, and once one of these reaches critical mass, the freeform accelerates toward it's conclusion.
The biggest problem here is that the intercharacter connections of an Australian Freeform really need twenty or more players before the critical mass can be attained. I've seen it work with as low as 15, but the success rate is far lower. I'd love to work a way of getting this style of play to work in a tabletop game of five players, perhaps the Jeepform collective requires some more exploration in this regard.