In a sense, the coastlines were the easy part. Sea captains (merchantmen and eventually organized naval expeditions of exploration like those of James Cook) made it their business to know coastlines and landmarks, in part to avoid shoals and other hazards. Their tools included the magnetic compass to establish direction, the sextant and chronometer to establish position in longitude and latitude-- and everything was minutely recorded in the ship's logs. A country's admiralty would have access to the logs and commission sea charts from these observations. Overland expeditions like that of Lewis and Clark or Zebulon Pike usually sketched their routes as they went, and as their reports were published cartographers were able to fill in the regions between coastlines with increasingly accurate maps. These parties usually followed rivers or established trails rather than following an arbitrary line, like the Mason-Dixon line. You can see from an ad in the back of Bowditch's American Navigator what a variety of sea charts were on offer at bookshops in 1802: https://archive.org/stream/newamericanpract00bowd The west coast of North America is conspicuously absent, perhaps because trade with the Spanish and Russian colonies there was not yet profitable for American merchantmen.