I too have often wondered about this, but there doesn't appear to be any concrete answer.
The introduction makes reference to Rogar, Ladril, Durgin and Telor as the 4 heroes of old that defeated Zargon in the past and now we have a new Barbarian, Elf, Dwarf and Wizard. Rogar, apparently wore the ancient Star of the West, but his counterpart is only asked to retrieve it from Barrok Tor so the Emperor can wear it... and apparently fail in his attempt to defeat Zargon.
Since we have Men, an Elf and a Dwarf coming together we can assume these 3 races are in good standing with eachother.
We learn a bit more about Dwarves from Keller's Keep that they had valor an ingenuity and that Belorn was their best known king. But Karak Varn had fallen into ruin and was taken over by the Orcs and goblins. We don't know if there's actually a Dwarven kingdom anymore. Perhaps all remaining Dwarves are refugees living among Men and Elves, and the Dwarven hero is joining the rest of the heroes to represent his fading people.
The nameless Emperor has a son named Magnus but there is no mention of a wife or queen. However there is an Elven Queen in Terellia, who has an evil sister that wishes to take the throne.
Though it has not been suggested that the Emperor and Terellia are married and just manage their respective kingdoms it is not impossible. Perhaps Terellia and the Emperor had a son (Magnus) and daughter (Millandriell), but neither's spouse is ever mentioned and in their marriage they chose to let the male heir rule over men and the female over Elves. Although this is possible it doesn't seem likely; Terellia's sister wants the Elven throne suggesting kingship would rely on lineage, and Sinestra would only be next in line if Terellia abdicates (this wouldn't necessarily rule out Millandriell's ascent, but perhaps she is too young and too kidnapped.)
The Elven Kingdom also appears to be doing much better economically as the Emperor is willing to pay heroes 240 gold for saving his "most powerful knight" while 900 gold coins can be found in a single chest in Mage of the Mirror.
The introduction does say that the 4 heroes are bonded by their loyalty to the Empire.
So even though the Elf has proven himself a champion to the Emperor, it doesn't appear to be good enough for Terellia. Although the Solo Quests were never playtested we can gesture that it would be a step for the Female Elf to prove herself; but you'd think the Male Elf already has, unless the Elven Kingdom isn't part of the empire, in which case Terellia force's him into a solo quest out of spite because he has already pledged loyalty to the Emperor. So therefore it seems unlikely that the Elf is from the Elven Kingdom, but an Elf living in the Empire. The introduction doesn't exactly say that the Elf is from the Elven Kingdom, but just that Terellia asked Mentor to find an Elven Hero. But since the Female Elf was included in Mage of the Mirror, which takes place in the Elven Kingdom, it can be conjectured that she is. Not necessarily bound to the rest of the heroes by friendship, but loyalty to either Terellia or Millandriell.
Next we have the Barbarian, where in his quest pack, actually says he's returned to the land of his youth. Apparently the Barbarian tribes are in the North and governed by a council of elders, who permitted the Barbarian to leave and travel. It can be assumed that the Barbarian, in his youth, showed great promise in swordsmanship and combat, as it is noted in his Character card, none can beat him in single combat. Perhaps Mentor noticed his potential and convinced the elders to allow the Barbarian to leave and express his talents elsewhere, recruiting him to save the Empire. He would have probably left on good terms since his return in the Frozen Horror is well received.
Doubtless the Emperor would have taken notice of the Barbarian, as he probably won multiple melee tournaments and bested several ordained knights. His success and champion status even in the Empire has made him renown to the land of his youth.
Any distinction between the male and female barbarians cannot be made as the introduction can apply to either one.
We know that the Male Barbarian has been away, proving himself a champion to the Empire, but considering the Female Barbarian figurine accompanies this expansion pack it is not unreasonable to assume that she is from the same place and shows skill in combat, much like the male Barbarian did. As she is interchangeable with her male counterpart and may join his companions in a quest it would seem she is trusted by them, so she must have some form of relationship to the Barbarian; either familial or other.
If the third solo quest is played by her, to rescue Gothar, the Great Elder it would seem likely that she knew him as well. Her back story, though, is much more uncertain.
No official back story is ever given to the Wizard, which is a shame as there is very little to draw from. He has no beard or any standard wizard garb that you'd find in this era, so it would seem that this wizard is still relatively young (unless his healing spells also reverse the aging process too). It appears as if the Wizard was never meant to be the main hero, but just play a supporting roll (Much like Telor was said to be with Rogar in the Introduction).
Based on the pictures and frontal designs of the game system and expansion packs, the Barbarian is featured front and center 4 times (Game System, Return of the Witch Lord, Frozen Horror, and Adventure Design Kit) while the wizard only appears in the background twice (Game System, and Wizard's of Morcar). The Wizard does wear a Creasent Moon and Stars on his jerkin. This Creasent Moon is also apparent on the High Mage's staff in Wizard's of Morcar, so it could be some type of symbol for a school of wizardry. Choas magic could be a corruption of the good and pure magic that this wizard practices. Though Choas Magic may seemingly be more powerful, as shown by Wardoz in Quest 7, it can be quite cancerous and will rot the mind if protective steps aren't taken.
This doesn't really help answer any backstory of how these characters came together, but part of that is for the player's controlling them to decide.
My group didn't necessarily create a backstory, though, as they gave their characters personality: the Barbarian is much like Conan and even talks like Arnold Schwarzenegger. The Dwarf is a former pirate that loves smoking cigars. The Elf is an arrogant bad-ass that complains whenever he takes falls into a trap. And the Wizard is a pansexual obsessed with feminine haircare products that may or may not be interested in the Elf...