Here is one explanation concerning how this myth may have started from About.com Genealogy:
During the 20th century it was common for Cherokee men to use an endearing term to refer to their wives that roughly translated as "princess." Many people believe this is how princess and Cherokee were joined in the popular Cherokee ancestry myth. Thus, the Cherokee princess may have really existed - not as royalty, but as a beloved and cherished wife. Some people also speculate that the myth was born in an attempt to overcome prejudice. For a white male marrying an Indian woman, a "Cherokee princess" may have been a little easier to swallow for the rest of the family.If you have any kind of similar family tradition, I would suggest you go to your local public library or get online and find a few books on the particular Indian tribe mentioned. One of the common issues I hear is that they ancestor came from a tribe that never lived in any of the places where the ancestors lived.
During the past years of helping people who claimed Indian ancestry, I only was able to verify the claim one time when we traced the family back to a grandmother who lived on a reservation in Oklahoma. Of course, Indian ancestry is not an issue if you are an Indian. It is also commonly believed that you cannot trace your Indian ancestry. Like any ancestral line, there will come a time when records are no longer available, but in most cases, especially in the western part of the United States, there are more records than most people know about or can possibly search.
For specific information, I suggest searching in the FamilySearch Research Wiki for native american or Indian articles. At last count there were over 3,700 articles about Indians and the various tribes across the United States with numerous links to additional resources.