This turned out to be a long one. Sorrynotsorry
1)
The two dwarfs and the half-orc fighter met in the army. The dwarf fighter was seeking redemption from the guilt of killing his own brother while the half-orc fighter depends on the cleric for spiritual guidance. The cleric himself saw too much suffering in the army camp to give a damn anymore, so the relationship between him and the other characters is probably deeply flawed on an emotional level, with the two fighters depending on a disillusioned cleric for their spiritual salvation.
The halfling monk was rescued from the orphanage by the tiefling monk. The halfling of course believes this is simply because the tiefling is an altogether good person, however the tiefling might just be after the tattoo and think it's easier to travel if the map carries itself.
The last three of our crew met in the bard’s home town. The sorcerer fled there when the drying of the swamp made that area uninhabitable. It wasn’t so much the sudden lack of water as the suddenly aggravated monsters with nowhere to live. An especially aggressive breed of giant swamp-rats gave the sorcerer some deep emotional scars as he fled for his life. The dragonborn simply entered the town one day and fell in love with the big, strong, passionate bard who was performing in the local tavern (8th night in a row, encores without being asked). The town finally grew tired of the antics the bard pulled and decided to throw him out. The sorcerer chose this time to make some rather pointed comments about racism and intolerance and was thrown out as well. Thinking they might stand a better chance of surviving if they cooperate, the bard and the sorcerer formed a strange friendship, the half-orc the centre of attention and the gnome always willing to lend a comment and some… Constructive criticism. Leaving naturally jived with the rangers ranging tendencies and the idea of travelling with the new object of her, rather one-sided, desires seemed too good an opportunity to pass up for the dragonborn.
Once, while walking through a forest, the constant chatter of the chipper halfling monk attracted the unwanted attention of the forest’s denizens. The monks had unbeknownst to them attracted a hungry dire bear and are now being hunted. The party meet as they are all traveling on the same forest road and the bear attacks. They are forced to work together or die alone as the dire bear attacks. Since it seems they are all heading in the same direction, they might as well travel together to the next town. (For clarification, adventure starts in medias res with initiative rolls as an appropriate number of dire bears charge)
The kingdoms of the area have long been engaged in an all-out religious conflict mainly encouraged by the two main churches. The war is at the moment a cold one and the services of the cleric and his fighter companions were no longer needed at the camp. Seeking a new purpose in life, the dwarf fighter notices the map on the halfling and asks him about it. The halfling starts spouting information about the treasure before the tiefling can intervene and the hunt for the artefact is on. Sensing a truly grand tale in the making, the bard is quick to offer his services and so the party is formed.
The tiefling is understandably displeased with this development, but as they spend the night in the next village she understands the importance of meatshields when unknown assassins attack the party and attempt to steal the halfling monk, dead or alive.
2)
Enter the big bad evil guy. The cleric should be able to identify some part of the assassins belongings or even their orders as coming from the leader of his church, Clavius Endragen. Apparently he wants the artefact as an edge in the next phase of the ongoing war, not unheard of and in all the conflict the life of a young halfling seems a small price to pay.
The sorcerer's swamp was devastated by the religious war, more precisely another artefact used to divert the flow of a river to drown an army. Whether or not he knows this is questionable, but the fighters and the cleric should know that letting the clergy get their hands on another powerful artefact will only mean the ending of more innocent lives. The tiefling of course wants the artefact for her own ends and the bard is just in it for the story while the halfling monk just wants to please everyone.
When the party leaves the village, or if they stay long enough, the village will get attacked by a major detachment of Clavius’ army as revenge for them daring to oppose his agents. How the party learns of this depends on their actions, but rumors should spread. There is no reason in performing a demonstration if no-one knows about it.
So as for tying the backstories together, the fighters and cleric fought in Clavius’ army and were rudely dismissed without their last pay, while the half-orcs piety is a direct cause of the religious focus of the societies. The sorcerer’s home was destroyed by Clavius’ actions during the recent campaign and the flood of refugees this caused was a direct factor in exiling the bard from his home town. The orphanage the halfling monk was “rescued” from was run by Clavius’ clergy, thus giving him knowledge of the map. The dragonborn seems to be a lone wanderer, but her father was a soldier in one of the wars and was killed when the ranger was only a young pup, leading to her daddy-issues and abandonment complexes.
The agents of Clavius will continue to hound the party at every turn, cementing the understanding that the characters must work together as a group if they wish to find the artefact and rid the land of the corrupt churches.
It seems like I already more or less answered the other points in the previous sections, but still.
3)
Other soldiers from the same army as the cleric and the fighters have also been laid off and have formed roaming bands of bandits that are terrorising the local farmsteads. Will the party help the farmers or their once brethren? Is there a way of saving the bandits and bring them back into the fold?
A village is suffering from drought as an effect of the river being diverted, same as with the sorcerer’s swamp. The watertable has shifted and even the wells are running dry. Can the party find the artefact and right these wrongs? Who will help the peasants in the meanwhile? Add in adorable war-orphans starving on the roadside.
A local priest is running an extortion racket, forcing the local farmers to pay more than their tenth or face conscription without support for their families.
A traveling merchant wants to hire protection for his caravan. When the merchant reaches his target village, he will attempt to sell food to the starving villagers for exorbitant prices. In the meanwhile all the food is on the brink of spoiling in the carts.
4)
Well I’ve already connected them in threes or twos quite overtly. However Clavius is either the dragonborns actual father who never returned or was the one who led her father to death in a pointless battle. Perhaps he actually killed her father, but now we’re getting into heavy cliched territory.
The dragonborn left the city she was born in because of her disillusionment with the faith, making her effectively a persona non grata in the city of ten thousand flags. During her travels she wandered into a swamp where she was attacked by the swamps denizens and almost killed, only to be rescued by a ranger who took her as an apprentice. This swamp just happened to be devastated when the warring forces decided to uproot an entire river. The dragonborn’s life was once again destroyed by religion and finally came to the realization that she could never live in peace while the clergy still ruled supreme.
The cleric was once a young and fervent believer, which gave him access to the cleric-training in the first place. He never met Clavius in person, but was given a special mission, said to come directly from the head of the clergy, to acquire an ancient artefact. This artefact was then used to uproot a river and caused the disillusionment of the cleric when he saw what destruction his action hath brought.
The half-orc fighter is also from the city of ten thousand flags and has heard stories of the blasphemous dragonborns. Luckily they were all cleansed from the city so that none of their taint could infect the pious and proper citizenry.
That should pretty much do it I think. If I haven’t lost your attention by now I thank you for reading that. I, at least, thoroughly enjoyed myself