The Empty Lands were the uninhabited continents (and islands?) to the east of Middle-earth: The Dark Land (a.k.a. South Land); and, beyond it, the Land of the Sun where the Sun rose over the Gates of Morning. The Numenoreans became great mariners and explored these lands but never seem to have founded colonies or outposts in them. When the Change of the World brought about the destruction of Numenor, Tolkien wrote that these lands formed the basis for new continents (although Karen Wynn Fonstad, in The Atlas of Middle-earth depicts the Dark Land as little-changed from its earlier incarnation). The Dark Land would have probably broken up to become principally Antarctica and Australia while the Uttermost East was likely swallowed by the newly emerged Pacific Ocean while the land-masses that would become the Americas rose beyond it. Perhaps new lands even appeared on the eastern coast of Middle-earth.
In our real world, humans from East Africa seem to have reached Australia and New Zealand around 40,000 years ago. In Tolkien's legendarium, Men only awoke in Middle-earth a little around 13,000 years ago. And as far as the histories of the Free Peoples relate, the Empty Lands remained uninhabited at least through the end of the Third Age. Or did they?
I'm speculating that Men from Harad and/or Rhun might have set forth from the eastern coasts of Middle-earth to settle in the New Lands as early as the last years of the Second Age, or at least soon after the fall of Sauron as a result of the Last Alliance of Elves and Men. This might have been about 9100 years before the present day. These might have been groups of Men fleeing from the tyranny of the servants of Sauron or simply unsettled by the coastal changes brought about by the Change of the World.
In game terms, I'm not sure that this has any relevance unless someone has taken up the career of a mariner and is exploring the further reaches of Arda (again, probably in the Fourth Age). This is the kind of thing that I would note as a background detail. I'm sure that the landmass(es) that would constitute the Americas would not remotely come into play, but this might not be the case for the regions that would come to include Indonesia, New Guinea, Australia and New Zealand. I could imagine a company befriending a 'Thorongil' in Rohan or Gondor who speaks of rumors he had heard in Far Harad of coastal tribes of Southrons who built fleets of large boats to flee eastward, seeking the Empty Lands, away from the dominion of the Enemy.
