DNA is best for connecting you to people, not to identifying ethnicities. Different companies use different reference panels and evaluate your ethnicity in slightly different ways, but if you have a measurable amount of Native American DNA it should show up regardless of which company you test with. If you believe you are the direct female descendant of a Native American woman a mitochondrial DNA test can probably confirm that. Companies that claim to connect you with a specific tribe are not actually able to do that. DNA cannot connect you to a specific tribe unless it shows that you are closely related to someone who is a citizen of a tribe.
The way to find a Native American ancestor is the same way you would find any other ancestor. Build your tree back with documentation as far as you can go.
If you have documented a direct ancestor who lived at a time and in a place where there were Native Americans, then search for a connection.