Many Pacific Northwest Native American communities "knew" that there were other lands besides their own. Nuxalk oral tradition gave the name of Miyaltwa to the lands to the far west, and this was understood to be the home of the salmon, and that the people who lived their wore salmon skin clothing (Boas, 1898). Nuxalk also had stories of people arriving from across the sea who wore grass clothing and stayed for 7 years before returning to where they had come from (Kopas, 1980, also personal communications), as well as origin stories that spoke of people traveling with their boats around the circle of the ocean to the far side. The stories of other nations (the Tsimshian for example, Boas: 1916) reference the land to the far west, usually in the context of traditional stories.

Given that many many many family stories begin with travels of first ancestors to the four directions and returning with goods from those locations, it would be better to say that most people "knew" that there was land on the other side of the ocean, but that that knowledge was largely not based on information in the recent past, and while some of it was likely based on contact, voyages, and long-standing oral history, some of that certainty could also have come from developing literary conventions related to how you told stories of voyages.