As previously mentioned, in the US the BIA (Bureau of Indian Affairs) is an excellent place to start your research. So is NARA (National Archives and Research Administration) and local state, county and city/town library and archives. Some city/town websites have an entire historical section dedicated to ancestry and the natives who once inhabited the area.
The Dawes Rolls and other related Rolls are excellent and valuable sources - the rolls give not only names and tribal associations, but also blood quantum's too.
"Indian school" records/files for the US are mostly available, those are another good place to search for info. Index cards for tribal affiliations and enrollment are another potential research resource - BUT there's several categories, such as those index cards that have been "accepted" and those which were "rejected". So be sure to search ALL categories.
If you know what tribe or band you're specifically looking for, you can always search them up and contact the tribe directly asking for further information and clarification (council members, genealogical services, administration services, etc.). From my experience, most are more than happy to assist, especially if you explain your reason why.
And of course, don't forget the US State census'! The US census library is available online at various sites and lists indigenous peoples separately for certain time periods. Libraries and archives hold copies, as well as some bigger genealogy sites like ancestry.com and family search.com (if I remember correctly).
There's Land and property allotment records are the other reliable records held at various institutions, including libraries and archives, as well as some local district Courts.
Lastly, some treaties also contain the actual names of the native signatories (particularly when transcribed online) - be it their given indigenous name or their birth name or both. So as a last resort, looking up local area historical treaties can sometimes be a help.
I recently went through this experience in depth trying to locate several family members and not too distant ancestors from tribes in Michigan, Indiana, Oklahoma and Illinois. I had no clue where I was going nor where to start, as I'm from Canada and am familiar with the resources up here only. BUT with patience, much research, and some reaching out to others for assistance in the US, I managed to be able to succeed in finding what (and who) I was looking for!!
So I truly hope you do find what you're looking for as well!