Each "Shard" is a shard of the gem of immortality that was shattered by the stranger.
The Lost Lands were found during the early years, the entrances broken open by the failed attempts of the FOA to cast Armageddon. The origin of the FoA was never really discerned, though we have hints.
Felucca is/was a "facet" of each of these shards. Nystul and Lord British found that the facet Trammel was un-populated, and forged links to the new lands, initially through moonstones and eventually through moongates. It has been speculated that Trammel was a mirror copy of Felucca at the moment in time that the moongate was first opened, perhaps in the same way the Shadow/Timelords recently opened up a moment in time in Moonglow.
Of course, one of the reasons they looked for the facet was for Lord British to give his people a way to escape Minax and the destructive factions that developed to cut Britannia into pieces. (One might suggest he was running from them, as many have.)
Once they had found this property of the shards, they commenced looking for other facets, the first of which was Ilshenar. Ilshenar's origin is still up for debate, but evidence would suggest that perhaps the FoA came to Felucca FROM Ilshenar -- where it appears Armageddon may have been partially cast at some far past time. It is likely that in this facet Lord British was killed during those battles and thus the entire land fell to ruin.
Next found was Malas. This facet was even more different than the others, seemingly the result if Armageddon had actually been cast. Filled with Necromancers and Paladins, it opened a new chapter in the shards. Eventually it was linked into the moongate network as well as Ilshenar.
Finally, the Tokuno Islands were rediscovered -- in Trammel. The Feluccans never searched for the Islands in their facet, or perhaps the people there don't wish to involve themselves in the political squabbles of the factions and thus keep themselves hidden. The peoples of Tokuno have a distinct civilization and their own abilities and powers, and the Empress ensures they stay that way.
Oops, I suppose I shouldn't forget the elves. They were rediscovered fairly recently, with various entrances to their hidden realm appearing through Britannia. The World Tree seems interconnected with Trammel AND Felucca, leading us to believe that there are elves also in Malas and Ilshenar.
With Lord British moving on to other worlds and Lord Blackthorn effectively dead, there has been no real governance for many years. As a consequence, the world has been slowly dissolving from the inside as people have no real leaders to look to in order to take them forward.
One begins to wonder if another Stranger will appear to help us pick a path?