As discussed in the comments on your question, there are two broad ways to answer this question. The equally broad answer to both is to examine how ensemble cast stories in TV, movie, and book series handle character backstories. Then decide which of the two methods you want to use.
Option 1: Integrate all the characters' backstories into a single overarching plot
In this version, all the characters' backstories are somehow tied together into a single storyline. This is generally very difficult to do unless you and your players specifically plan for it. Otherwise, it ends up feeling like a series of (often very contrived) coincidences that happen to somehow tie all the characters together. This may not be a bad thing, depending on the genre you're going for - it works well in suspense, horror, and/or mystery, where the focus of the story is the suspense or mystery surrounding the characters' connected histories. (I believe this is how Lost worked, though I haven't watched more than the first two seasons so I'm not sure.) In your standard fantasy or sci-fi story, however, it's likely to just feel awkward or forced.
If you want to go this route, and you don't want the focus of the story to be the players discovering all the ways they're unexpectedly connected, then plan character connections in advance with your players. Make sure that each character has some link to one or more of the other characters, and work with the players to craft backstories that both suit your end goal and have hooks you can exploit to get there.
Option 2: Each character's backstory is integrated into the broader story, but not necessarily at the same time.
This is what you most often see in ensemble cast stories. For example, in both the Star Wars and Pirates of the Caribbean movies, the main characters' backstories all play important roles at some point or another, but not all at the same time, and not all for the same plotline. Han Solo's history with Jabba, for example, has nothing to do with the end goal of stopping Darth Vader and the Empire, but it still has a major effect on the overall story, since Luke and Leia have to spend time and resources rescuing him. Likewise, in PotC, Jack Sparrow's history with Davy Jones has no tangible effect in the first movie, but drives the plot of the second. Will Turner's relationship with his father Bootstrap drives the story of the first movie, as it's his blood needed for the curse, but comes back in the second and third movies to be relevant in smaller ways that aren't tied directly to the main goal.
To achieve a similar effect in an RPG, find little ways to weave in parts of the characters' backstories here and there. Drop small hints and teasers of various characters' backstories early on, but don't push it (perhaps an enemy they've killed, as he dies, says to the paladin, "Just... like... your father"). The players may or may not pursue these small hints; follow their lead. If they do, great - you can now send them on a quest to find out how the villain knew the paladin's father. If they don't pursue the hints, then open up one of the hints into a full-blown plot that's tied closely to the players' current goals.
Example:
In a game I recently finished, we had a bard, a rogue, a swordmage, and a pair of assassin twins. The bard's story drove the plot at first, as she sought a better home for her people - but this meant going on a quest for which she needed the rogue's family's resources. The assassin twins joined the group on a mission to kill the bard (a mission drawn from their own backstory), but scuttled those plans when they discovered they actually kind of liked her. The swordmage had an on-again off-again side quest to become ruler of his clan and protect his village; this became plot-relevant later in the game when we needed an army and the swordmage was able to summon his clan to our assistance.
In that game, none of our backstories were directly related to the overarching plot, which involved stopping Lolth from taking over the world. But all of us had times - sometimes just a moment or two, sometimes a full side quest - when our backstories were extremely relevant to what we were doing at that moment. This isn't a "one adventure per character" setup - you can weave parts of multiple characters' histories into the same plotline, addressing this pair of characters here and that trio of characters there. If your fighter is from a family of merchants, allow him to use his contacts to advance a plot related to goods or travel. If your bard and your wizard are from the same city, set a plotline in that city and weave in their families. When they come back to that city later, have their favorite (or least favorite) NPCs greet them. And so on.
Your characters live in the world of your game. As such, bits and pieces of their histories will naturally become relevant as they move through the various plotlines - but not all at once, and not necessarily to drive the main story.