You won't find birth certificates for them because most Native Americans didn't have a written language. Not even caucasians were issuing birth certificates that early.
You have to search for them until you find them living with the Native Americans. Then You can identify the Nation (Creek, Choctaw, etc.). Then you contact that Nation by doing a Google search (Creek Nation, etc.). They will be able to tell you if your family members belonged to their Nation or not.
A lot of people think they have Native American heritage but you have LOTS of it! Successful Searching!