The short answer to your question "Was the arrival of European settlers a surprise to every single Native American as they moved west?" is no, but trying to come up with a cohesive explanation is a bit more difficult. Europeans didn't travel in a single westward marching wave across North America. Europeans were poking around all over the Americas in the 16th Century - the English even landed in California decades before they got a permanent colony up and running on the east coast (Francis Drake landed near what's now San Francisco in 1579). The people of Colorado would have first heard of Europeans not from the east, but from the south, as Coronado's entrada marched up from Mexico into Arizona, before turning east across New Mexico and eventually into Kansas in the early 1540s (map - note: the labels of Native nations are anachronistic; almost all should be elsewhere in the 1540s). We know news of this event reached into Arkansas / eastern Texas, because the survivors of de Soto's entrada eventually heard about it. Speaking of de Soto, as he winded his way through the Southeast (map) at the same time, we know that news of his entrada preceded him. The Apalachee in northern Florida had evacuated their capital and set an ambush for him; Cofitachequi dispatched ambassadors; Tuskaloosa also set an ambush for him and sent spies among his porters. And, of course, there had been early Europeans in the area as well. Coronado and de Soto were both inspired by the tales of Cabeza de Vaca (map), who was one of the few survivors of the Narvaez entrada. When de Soto reached Cofitachequi, he found Spanish items there, probably from Allyon's attempt to colonize the southern coast of South Carolina years around the same time as Narvaez' folly in Florida. Going back to nearly the beginning of European-American contact, it seems the Calusa of southern Florida learned of the Spanish from Taino refugees who fled Cuba during the Spanish conquest of the island. Further north, Cartier overwintered in Stadacona (Quebec City) in 1535, after voyaging up the St. Lawrence as far as Hochelaga (Montreal); during his stay there the local leader - Donnacona - was noted to have made frequent visits to neighboring nations to the south, often returning in the company of strangers. It seems like he was definitely making sure everyone in the area knew what was going on.

I know that trade among the tribes was a regular occurrence. But how far did that go? [...] I've heard that western diseases like smallpox traveled 10-20 miles ahead of the people carrying them as the westward expansion continued; is that true? How can a disease spread with nobody to carry it?

I'm going to link these questions together, because think they can best be illustrated with some examples from the Ohio River valley. On many maps that attempt to illustrate the nations that existed in North America prior to European colonization, the Ohio Valley is oddly vacant (see here and here for examples). This isn't because no one was living there, at the time, but because the demographics were highly disrupted immediately prior the European explorers actually reaching the area. There were several prominent archaeological and proto-historic cultures in the area such as the Caborn-Welborn in southern Indiana, the Fort Ancients in Ohio and Kentucky (at least some of whom are synonymous with the Shawnee of the time), and the Monongahela in West Virginia and southwestern Pennsylvania. The Caborn-Welborn and the Fort Ancient don't seem to have had direct contact with Europeans - at least no substantial contact. But they did have European trade goods. These European-derived artifacts most likely came through Native middlemen, such as the Monongahela, who were very likely the same people as the historic Massawomeck, a large non-Algonquian confederacy that lived in mountains to the northwest of Virginia and used the Potomac as their main route to trade with the English prior to the 1635. In the mid-1630s, the Massawomeck disappear from the historical record, and the archaeological cultures of the Ohio Valley start to crumble too. Perhaps coincidentally - or perhaps not - the first major smallpox epidemic in what's now the US began in New England in 1633. Just as Native traders had carried European goods into the Ohio Valley, they would have also carried European diseases with them. Of course, we can't be certain that smallpox is the blame here; a few years later, both influenza and smallpox would hit the Wendat (Huron) north of Lake Erie. In that case, we know patient zero for that outbreak picked up smallpox after traveling to Montreal. In the Ohio Valley too, it was likely a handful of different diseases in succession that caused the initial disruption of local communities, followed eventually by the Beaver Wars in the 1650s, all happening with just outside the awareness of Europeans.

Taking a quick detour from North America for the moment, a similar situation happened in Australia during the smallpox outbreak of the late 1780s into the 1790s. Indigenous messengers ran ahead of the colonists and the disease, spreading news of both and unfortunately spreading the disease as well.

Did the Native Americans correlate that the proliferation of smallpox meant that people from another land were coming to take over?

Going back to the situation among the Wendat, it's quite clear that they linked these disease with the arrival of Europeans. As the French missionary Jerome Lalemant wrote during the 1639 outbreak of smallpox:

[The Wendat] observed, with some basis in reason, that since our arrival in these lands, those who were nearest to us happened to be those most ruined by the diseases and that the towns that welcomed us now appeared utterly exterminated. [...] In a word, we were dreaded as the greatest sorcerers on earth. Wherein truly it must be acknowledged that these poor people are in some sense excusable. For it has happened very often, and has been remarked more than a hundred times, that where we were most welcome and baptized the greatest number of people was in fact where the greatest number died. Conversely, in the cabins to which we were denied entrance, through they were sometimes extremely sick, at the end of a few days one saw every person happily cured.

The link between Europeans and the new diseases eventually led to the Wendat banishing the French missionaries to peripheral communities; they might have been killed outright had the Wendat council not wished to maintain their alliance with the French.

When you say "settlers" do you mean people intending to settle on or near Native American land? Because there were non-settlers who visited Native Americans long before settlers arrived - hunters and trappers, for instance, and on the West coast, sailors.

I've not read a lot on this area, but not too long ago I did read Undaunted Courage, which was about Louis and Clarks expedition. They weren't settlers, but rather explorers. And they did not encounter any Native Americans who were unaware of the white man. Hell, most of them had guns and goods from the white man by that point.