I don't have the expertise to give a full answer but I can provide a skeleton for others to build on. There was not a single pattern for western settlement/land acquisition during the colonial era and the early 1800s. There were outright illegal means, legal means, and "legal" means.
First, a lot of colonists simply squatted, meaning they moved west, found apparently unoccupied land (they may or may not know if they were encroaching on any specific Native American tribe), and settled on it without any legal or legitimate claim to it beyond their literal presence. This could get them in trouble with white legal authorities and/or with the Native Americans themselves. Take a look at the Proclamation of 1763 line in which the British government tried to curb westward settlement. Not only did it do very little to curb westward expansion but it also proved very contentious with land-hungry colonists.
Second, a lot of land was divided and sold via land speculators who may or may not ever actually see the western lands they dealt in. Basic model: a wealthy many buys up thousands of acres in, say, Ohio, then organizes it into individual parcels that he then tries to sell for a net profit. These speculators tended to be wealthy elites in the established colonies (quite a few founding fathers dabbled in it) and you can imagine how they might oppose squatters who could muck up the process. But of course, the only land they were supposed to be speculating on was land legally obtained by colonial/state governments, which brings us to:
"Legal" means: a lot of Native American land was obtained unfairly, and that's putting it mildly. A tribal leader refuses to cede land in a treaty, so white colonials go to his relative or even his rival, get permission from them, then call it legit. See also examples like the Walking Purchase of 1837, in which the Penn family used underhanded tactics to claim a Rhode Island-sized piece of native land in eastern PA, far beyond what the Delawares believed they would be giving up. Beyond tactics like these was coercion using western goods like alcohol and outright violence. Colonists relied on any pretense they could to make land claims legal, however questionable.
Some books:
Taylor, William Cooper's Town (details the activities of a famous land speculator as a case study)
Holton, Unruly Americans
Holton, Forced Founders
Dowd, A Spirited Resistance (focuses on Native American religious cooperation in the face of white expansion)
With regard to the question: "What about those pesky Indians?", in the far west, it was largely a crapshoot. In a lot of areas, natives were terrified and preferred to move aside, especially in areas where militias were used and bounties offered. For example, in Northern California following the initial massacres on the coast and in mining country, natives were pretty wary. Some moved to ore remote areas and avoided white settlements. In other areas, and/or at different times, being in newly settled land was a high risk proposition. Several uprisings followed initial white settlement, like the Bald Hills, Modoc and Rogue River Wars of the 1850/70s. Some of these were protracted, low level conflicts that would have kept settlers pretty nervous. In the larger picture, the Native insurrections were sparse and limited in duration ending with forced movement of Native Californians to local and very distant reservations. The Modoc, for example, occupy reservations in both Oregon and Oklahoma. See A. Bledsoe, Indian Wars of the Northwest: A California Sketch, 1885.