Thank you for posting your question on the History Hub.
You can get started searching for your relative at American Indian Records in the National Archives. You can search your Cherokee ancestors in the digitized Dawes Rolls in the National Archives Catalog.
The Cherokee Emigration Rolls that may be of interest to your research, but have not been fully digitized in the Catalog. For access to and/or copies of the non-digitized part of this series, please contact the National Archives at Washington, DC - Textual Reference (RDT1) via email at firstname.lastname@example.org. When emailing the staff, please include as much detailed information as possible.
In addition, you may search family members on familysearch.org for free after registration. You may search the wiki pages for useful search information such as these pages for Cherokee Nation or Native American Genealogy.
Another option is to contact the Cherokee Nation directly. As a reminder, the National Archives is only the custodian of US Government records and does not retain any vital records for birth, death, divorce or marriage.
I hope this is helpful in beginning your research into your grandfather!