The Supreme Court of Canada has stated that it would not hear an appeal in the case where a native Mi'kmaq woman was called Kemosabe, and that it is not "overtly racial".

The person who said this says that he things it meant "faithful friend". However, it seems there is a lot of disagreement of what it means.

One thing for sure: the term as popularized in mass media was first used in the Lone Ranger radio show in 1932, and then in the 1950s Lone Ranger series on TV later.

The Straight Dope has a nice article on possible meanings and origins. The most likely meaning is "scout" in Ojibway.

An interesting side point is how the media has stereotyped Native American Indians for a long time, from the Cowboys-vs-Indians Westerns of John Wayne, and were only portrayed positively in Dances with Wolves. But that is another article.