What is the principle of Tribal Sovereignty? Does it mean that Native American tribes are not part of the United States?
Yes, the federal government considers Native peoples to be part of the U.S., accords them citizenship, and extends a special type of self-governing authority to the nations.
The federal government accords recognized Native American groups a special type of self-governing authority: that of "domestic dependent nations." Cherokee Nation v. Georgia, 30 U.S. 1 (1831). Federal laws and court cases have worked out the extent of that authority over the years, but the Department of the Interior maintains a topical FAQ page that helps to summarize it. Wikipedia has a nice article on the subject, too.
This sovereignty does not mean that Native Americans aren't (also) citizens of the United States. See Indian Citizenship Act, 43 Stat. 253 (1924). Prior to the 1924 Act, the federal government had previously granted some forms of citizenship via treaty and assorted acts of Congress.
When it comes to the states, the relationship can be murkier. An early court case, Worcester v. Georgia, 31 U.S. 515 (1832), struck down a state law regarding Native lands and laid out much of the relationship between Native peoples, the federal government, and the states. While the text of Article I, § 8 of the U.S. Constitution is limited (it vests plenary power in the Congress to regulate commerce with Native peoples), courts have interpreted it to mean that states have no authority to regulate Native matters absent explicit authority from Congress. One of these explicit exceptions involves Public Law 280, which grants certain states civil and criminal jurisdiction for certain matters that may involve Native Americans. Subsequent cases have refined this relationship over time. For example, Native sovereignty may take priority over certain state-level powers, like that of search and seizure. See Inyo County v. Paiute-Shoshone Indians of the Bishop Community, 588 U.S. 701 (2003).
Since the Indian Citizenship Act of 1924 was passed, all Native Americans born within the US have been citizens by birth. Prior to this act Native Americans were in many ways treated as foreigners by the US. They were not citizens by birth, and their tribes had some but not all of the attributes of independent nations. The latter is still true, But I belie to a reduced degree.
The text of the law is:
Be it enacted by the Senate and House of Representatives of the United States of America in Congress assembled, That all non citizen Indians born within the territorial limits of the United States be, and they are hereby, declared to be citizens of the United States: Provided That the granting of such citizenship shall not in any manner impair or otherwise affect the right of any Indian to tribal or other property.
The OP asks if the Native American nations are considered "Part of the United States".There is no single, simple answer, as I understand it.
The various "Indian Reservations" have been considered geograpically part of the united states since they were created. Federal officials (mostly the FBI) can and do go there to enforce Federal laws, and did so before 1924, as well. State and local law enforcement have more limited jurisdiction. I belive this varies from one reservation to another, but on most of the larger reservations, day-to-day law enforcement and government are left mostly to the tribal authorities.
People who are born on a reservation are US citizens from birth. (Before 1924 this did not apply to members of tribes, but did apply to non-members.)
Natiive Americans born within the US are citizens, and have been since 1924. In addition, the US Bureau of Indian Affairs (BIA) has excersized a level of control over native americans that neither federal nor state governments have over any one else in the US. Most notoriously, children were encouraged and in many cases forced to attend the American Indian boarding schools run by the government or by various churches. There children were isolated from their families, forced to change their names, speak English exclusivvely, and generally avoid native culture. In many cases they were subject to physical and sexual abuse, as well. The Wikipedia artcle says:
Federal legislation required Native American children to be educated according to Anglo-American settler-colonial standards. Parents had to authorize their children's attendance at boarding schools, and if they refused officials could use coercion to gain a quota of students from any given reservation.
Such requirements were not, and probably could not have been, constitutionaly, imposed on any other group.
Prior to 1924, I believe that native Americans were not included in the population figures which were used in computing the allocation nof congressional represenatives.
For some purposes, the various Native American tribes were treated as separate nations. Most obviously, treaties were negociated and signed with various tribes. Treaties are not normally signed with a group that is part of a country, rather treaties are signed with other countries. On the other hand, the various tribes were not regarded as independant. For example, they were not allowqed to have separate relations with other non-US nations, or even with other tribes. The term "dependant nations" has been used for this status.
I don't know of another arrangement which is or was quite the same as that between the US Federal government and the various tribes. Perhaps the closest analogy was the relation between the British Imperial government and various nations that had "accepted" the "protection" of the Empire, sch as some of the Indian states who retained their own rulers and governmetns, but had no independant foreign policy or foreign relations. Some parts of Polynesia had simialr arrangements, i understand.
The various Native American tribes and their members were neither regarded as fully a part of the United States, nor as fully separate. The question can ony be answered in the context of a specific purpose or aspect of participation in the US.