Seafarers, perhaps, most likely from northwestern Europe. We know well that there were people living along the coastlines; we have cave paintings of marine animals in France and Spain. And the people could well have built skin boats and "island-hopped" along the shore (now the bottom of the Atlantic continental shelf 200-300 feet below sea level). About 50-60,000 years ago, people crossed at least 90 miles of deep ocean from Sunda (modern-day Indonesia) to get to Sahul (present-day Australia and New Guinea.)
One wonders about the discovery of haplogroup X (a European/Middle Eastern genetic trait, absent in most Siberian populations) in precolumbian Indians, and the similarities between the technology and material culture of Clovis and the Solutrian culture of Atlantic Europe at about this time.
The flood stories do seem to reflect time periods postdating the Ice Age. Some flood stories in SE Asia may reflect what happened to Sunda; the Black Sea flood is probably reflected in Greek myth (the Deukalion legend) and in Sumerian and Semitic legends (Gilgamesh and Noah, respectively). The Black Sea flood occurred several thousand years after the end of the Pleistocene (5600 BC versus 9000 BC) but resulted from rising sea levels after the collapse of the Laurentide Ice Sheet in the North Atlantic. The Black Sea, between the end of the Pleistocene and 5600 BC, had been a lake, and was probably a center for Neolithic communities.
BTW, the Mediterranean originated about 5 million years ago, long before any humans existed.
As for multiple migrations to the Americas, that makes sense, based on the skeletons (Eurasian types at Kennewick and Spirit Cave, Australoids in Brazil at Lapa Vermelha). Genetic evidence is tougher, though.
Ancient Hearths To Test Carbon Dating (Humans In Brazil 56K+ Years Ago)
"Out of seven Pedra Furada charcoal samples scientists took from the hearth structures in the deepest layers, five were beyond the limit of the ABOX technique itself, returning ages greater than 56,000 years, the report said. Analysis of the final two samples gave finite ages of 53,000 and 55,000 years."
