I found this article about contacts between the Norsemen and the indigenous people of the Americas by Valerie Hansen at Aeon extremely interesting:
Who, besides the indigenous peoples from Asia who crossed the Alaskan land bridge in prehistory, arrived in the Americas before Columbus? The question has fascinated generations of scholars. Could a Chinese tribute ship, as Gavin Menzies proposed in 2002, have departed from the rest of the Ming fleet in East Africa in 1421 and sailed to North and South America, Australia and the Arctic? Could fishing vessels from the British port of Bristol, as David Beers Quinn suggested in 1974, have followed schools of cod across the north Atlantic and reached the fishing grounds off the Canadian shore in 1480 or 1481? No persuasive evidence supports the claim about the 15th-century Chinese. The voyages of the Bristol cod fishermen are more likely, but no documentation concerning them predates 1492, possibly because they wanted to keep the location of the fishing grounds secret.
The most credible claim – that the Vikings reached North America around the year 1000 – deserves more attention.
The short version is
- the evidence that the Norsemen actually reached the New World before Columbus is pretty good and getting better all of the time
- the indigenous people of the Americas had extensive trade routes long before Columbus
- the Norsemen may well have penetrated the interior of the country as well as having short-lived settlements on the coast