As far as I know, citizens from Indian reservations can vote for president, but every-time we see discussions about Presidential elections, votes are assigned by the electoral college per state. How do their votes for President count? Are they assigned to a particular state?
Native Americans (like everyone else) register to vote in the state they are physically based in -- if they can provide an address, which can be difficult. Voter registration rules differ between states.
Many Native Americans, especially those who live on reservations, do not have traditional street addresses. This has resulted in voter registration applications being rejected in many states.
County by county, election administrators must know exactly where voters live to assign accurate precincts, which then determine which ballot a voter receives, which offices she votes for and at which polling location she casts a ballot. In Utah and many other largely rural states, residents can register to vote by describing their approximate location on registration forms, or even draw a rudimentary map, which is allowed by the National Voter Registration Act of 1993.