Nation states are sovereign, but they don't necessarily own much of the land within their borders; most land is held by individuals, or organizations, such as the medieval church, etc.
The conquest of the Americas brought the laws of European nations, most of which derived ultimately from either Roman law, or the English common law. Under these codes, any land with no recognized owner was property of the state. Such land is often barren, and thus unused, and thus not significant, except to nomadic peoples, such as the herders of the northern reaches of Europe and Asia, or by the aborigines of Australia, or the hunter-part time farmers north of meso-America.
The concept of sovereign ownership of land by the natives of North America follows from these issues, as a legal purchase of land from a sovereign group, or a collection of sovereign groups with over-lapping seasonal claims, was used to extinguish the native titles, and thus prepare the land for sub-division and future sale to European-descended settlers.
You can see this in action in the Detroit area of Michigan, from the time of Cadillac's arrival, and purchase of land for Fort Pontchartrain, at "De Troits", the straits. The English continued this policy, and extended the area of settlement slightly, and permitted the local "habitants" to privately extend the claims, as long as there was a proper Indian deed; see for example Grosse Ile, purchased in 1776 by the Macomb brothers. The American's continued this process after they took control in 1796. Negotiations often followed armed conflicts, such as Wayne's victory at the Battle of Fallen Timbers, and after the War of 1812.
The typical purchase price for cession of land rights was (1) continued usage for hunting and fishing, (2) an annuity, paid annually in money, but mostly in goods, and (3) creation of a reserved area, which was to be limited to Indian use, with traders as permitted.
Two other points: the local Indian tribes used their traditional laws for intra-tribal disputes, and the federal courts for disputes between tribal members and Americans; also, those living in tribal areas were untaxed.