Turns out, they have no real sovereignty at all, depending on how the Federal government wants to rule. Here's an excerpt, followed by the link:

"in 1973, the federal district court for the district of Montana stated the underlying principle in the case of United States v. Blackfeet Tribe, 364 F.Supp. 192. The facts were simple: The Blackfeet Business Council passed a resolution authorizing gambling on the reservation and the licensing of slot machines. An FBI agent seized four machines. The Blackfeet Tribal Court issued an order restraining all persons from removing the seized articles from the reservation. The FBI agent, after consultation with the United States Attorney, removed the machines from the reservation. A tribal judge then ordered the U.S. Attorney to show cause why he should not be cited for contempt of the tribal court. The U.S. Attorney applied to federal court for an injunction to block the contempt citations. The Blackfeet Tribe argued that it is sovereign and that the jurisdiction of the tribal court flows directly from this sovereignty. The federal court said:

No doubt the Indian tribes were at one time sovereign and even now the tribes are sometimes described as being sovereign. The blunt fact, however, is that an Indian tribe is sovereign to the extent that the United States permits it to be sovereign -- neither more nor less. [364 F.Supp. at 194.]
The court explained:

While for many years the United States recognized some elements of sovereignty in the Indian tribes and dealt with them by treaty, Congress by Act of March 3, 1871 (16 Stat. 566, 25 U.S.C. s 71), prohibited the further recognition of Indian tribes as independent nations. Thereafter the Indians and the Indian tribes were regulated by acts of Congress. The power of Congress to govern by statute rather than treaty has been sustained. United States v. Kagama, 118 U.S. 375, 6 S.Ct. 1109, 30 L.Ed. 228 (1886). That power is a plenary power (Matter of Heff, 197 U.S. 488, 25 S.Ct. 506, 49 L.Ed. 848 (1905)) and in its exercise Congress is supreme. United States v. Nice, 241 U.S. 591, 36 S.Ct. 696, 60 L.Ed. 1192 (1916). It follows that any tribal ordinance permitting or purporting to permit what Congress forbids is void. ... It is beyond the power of the tribe to in any way regulate, limit, or restrict a federal law officer in the performance of his duties, and the tribe having no such power the tribal court can have none. [Id.]"

http://www.umass.edu/legal/derrico/nowyouseeit.html