I was once a tribal cop, and this issue came up now and again.
Each tribe sets the rules on how local and federal law enforcement operate on the reservation, within limits. The FBI has exclusive jurisdiction for about 20 serious crimes on Indian land such as murder, rape, robbery, etc., and will come in and take over any investigation when and if those crimes occur. Some tribes don't have their own law enforcement, and allow the local sheriff's or police department to operate there as if the land wasn't a reservation. Others that do have their own tribal police departments still permit local law enforcement to operate "business as usual" where non-Indians on shared lands are concerned.
For example, the reservation where I worked had two state highways that passed through the reservation. These were patrolled by the state highway patrol and occasionally the local sheriff's office (the reservation overlaid four counties, so which sheriff's office might be there depended on where you were). If you were a non-Indian and were stopped by the highway patrol on one of the state highways on the reservation, the stop would be handled as if it took place anywhere else, and the charge would be heard in state court. If the driver was an Indian, tribal law applied. The trooper could, at best, hold the driver and request a tribal police unit to respond. The tribal officer could then issue a citation on behalf of the trooper. In essence, the trooper would be making a citizen's arrest. The charge would be heard in tribal court.
The tribal officer could also elect to do nothing at all. Tribal governments are notoriously political, and taking enforcement action against a favored person, such as the tribal chairman's nephew, could be fatal to one's career.
A tribal officer taking enforcement action against a non-Indian on tribal lands would also have the charge heard in tribal court, assuming the tribe had a relevant law to apply to the act. If the act was not addressed by tribal law, the charge could be brought in state court. This didn't happen a lot.
A tribal member who had an arrest warrant issued in state court was immune from arrest so long as he remained on the reservation and the tribal court didn't endorse the warrant. If the tribal court did endorse the warrant, the tribal police could arrest the tribal member and deliver him to the custody of the local police. The tribal courts seldom endorsed state warrants.
If a non-Indian fled to the reservation to avoid arrest on a state warrant, what would typically happen would be that the local police would contact the tribal cops and advise them of the situation. Then, the tribal cops, without or without the locals in tow, would go arrest the subject of the warrant and turn him over to the local police. If a non-Indian was fleeing from the local cops and entered the reservation, the local cops could continue the pursuit and make the arrest just as if they were anywhere else, under the "fresh pursuit" doctrine. Extradition proceedings would not normally be required unless the pursuit had crossed a state line.
Most tribal members who were state fugitives hanging out on the rez weren't very good tribal citizens, either, and were not pals with the tribal police. It wasn't uncommon for Joe Fugitive to go to town for a dentist's appointment and have the local cops tipped off by the tribal police as to when and where he would be. The second he stepped off the reservation, he was fair game.
By the way, you may notice that I don't use the term "Native American." All of the people I met on the reservation referred themselves as "Indians" or 'Paiutes," so I did, too. I know that's not the custom everywhere.
More questions on legal issues: