To complicate matters, there was more than one route involved in the "Trail of Tears." (I've visited some Trail of Tears historic sites in the last few years, on multiple routes...)
Was your ancestor Cherokee? (The "Trail" isn't restricted to Cherokee. Some other tribes were also "removed.") Do you know where he would have started from? With clues like that, you may not be able to find a grave, but at least you may find some clues to the route that he likely traveled.