Ordinarily, my group tends to do a lot of backstory for their characters, and we interweave them with things that make them more than a bunch of guys that meet at a tavern, then start adventuring. This is not necessarily the way to go about things, but most of our games tend to be either modern(ish) pulp fiction games, or space opera.
How much backstory is enough or too much? Depends on what you need for the story. Some characters can have a pages long backstory with all sorts of things the dungeon master can hook into for plots. Or it could be something simple, like Indiana Jones, for instance: he’s an archeologist with a reputation. He’s a bit shady, was in love with a character he will encounter, and isn’t afraid of much save snakes. Go!
So how to give characters interconnections that make them not just want to travel together, but give them common purpose?
The first way is to have them be in the employ of a particular NPC or organization. This works very well in military, police, or spy -oriented games very well, but might not fly in a D&D game, depending on the classes you’ve chosen. It also works to give the characters purpose for their adventure. Simply put, you got orders.
An example of this might be the town garrison of a city. Warriors have an obvious role here, but so do rangers and rogues — who could both be used as scouts or spies. Clerics as medics; wizards as artillery or leadership. For whatever reason, they’ve joined up — be it honor, money, love, adventure, religion.
Or maybe they’re all from the same town. This can be a bit difficult if they are all different species/races in D&D. Why are elves, dwarves, and humans all residents of the town? The explanation can be pieced together by the DM, or it can be a join effort. Maybe it is an trading post on the edge of various territories — a medieval Casablanca or Babylon 5. Maybe it’s a major city, like Venice was in the 14th Century, bringing people together.
Maybe some are related. Obvious linkage.
Or they could have different reasons to go after the Big Bad™. Maybe he has one of he character’s loved ones hostage, or has some McGuffin you need for one of the characters (like, say, a scroll for the wizard) — they could come together because they (or at least some of them) have a common enemy.