I have had several researchers tell me they have Native American roots and were trying to research that possible connection. Sadly, it isn’t as easyresearch project as it should be, partly due to the culture of Native American’s and partly due to our government.
There is a site out there that can get you started in the right direction if you know or have an idea of the tribal nation your relative belonged to. Native American Nations has pages listed for many tribes, which may help you find a resource in locating that link to your suspected Native American lineage.
Ancestry.com also holds the US Indian Census rolls from 1885-1940. For a fee, you can search those records, keeping in mind, they do not contain the amount of information the regular census does.