Dear Ms Hernandez,
Thank you for posting your request on History Hub!
Given the historically recent use of surnames within tribes, the current list of 23 federally recognized tribal nations within the borders of New Mexico should suffice. NARA is unaware of any tribal nations recognized by the state that are not recognized by the federal government.
Please note that prior to 1900, many nomadic tribes considered the lands of New Mexico home while some, like the various Pueblos, developed villages which existed for thousands of years in the same places.
We hope this is helpful. Best of luck with your research!
[Information provided by Cody White, Subject Matter Expert]