I guess no one answered the question since you can find the answer very easily at the German wikipedia.de-site. However, if you do not understand German, this will be of little help...
So I will try to tell you in English. The names Old Surehand and Old Shatterhand are supposed to be the English translation of Indian war-names with which some native Americans chose to honour those two fellows for their extraordinary abilities both as warriors and scouts - or "westmen"/"Westmänner", as Karl May would have called them. He used the term "westmen" as a similar to both "scout" or "backwood people", referring to people who would have no problem making their living even in the wilderness of the old west. (May had probably picked up the term "westman" from a translation of George Ruxton "Life in the far west", which he knew pretty well.) He also believed that the prefix "Old" was not necessarily used to describe the age of a person, but could also refer to his reliabilty and his tested skills as a "westman" (scout). Actually, he had picked up the prefix "Old" from the character "Old Rube" in Mayne Reid's novel "The scalphunters".
Old Shatterhand is usually referred to as Karl May's own "alter ego", since most of his novels are told in first-person from the perspective of Old Shatterhand. May imagined this Old Shatterhand - or himself - to have been a young intellectual, "Dr. Karl May" from Germany who had studied Foreign languages and religion and had come to America to seek first hand experience. Usually going by the name of "Charly" or "Mr. Charles", he then worked for a railway company where he met the old scout (or "Westman") Sam Hawkens (another character inspired by Mayne Reid's "Old Rube" from "Scalphunters", while the cinematic interpretation by Ralf Wolter is of course inspired by Gabby Hayes and Al St. John's character "Fuzzy" who, after WWII had become extremely popular both in Germany and Italy - note that Leone used lot of "Fuzzy"-characters too, and even named his villains after Fuzzy's companions "Billy Carson" and "Marshall Cheyenne"!). Sam Hawkens taught the young greenhorn Charly how to hunt mustangs and buffalo and gave him the nickname "Old Shatterhand" which later became his war name among the native Americans. Soon, young "Old Shatterhand" killed a Grizzly bear who had intruded the railway's working camp. During the struggle over who had actually struck the final blow, an old white friend of the negotiating Mescaleros Apaches nearby was killed. Winnetou's father Intschu Tschuna, the Mescalero chief, declared war both on the railway and everyone working for it, includig the scout Sam Hawkens and Old Shatterhand. Only after fighting for his life and saving both Intschu Tschuna and Winnetou, Old Shatterhand could finally win both Winnetou's friendship and the love of his sister Nscho Tschi. The planned marriage between Old Shatterhand and Nscho Tschi never took place because Intschu Tschuna and Nscho Tschi were killed by the white bandit Santer. Old Shatterhand however could persuade Winnetou not to seek vengeance and bloodshed from all white people but instead go with him to hunt down the only actual murderer of his sister, Santer. (They succeeded however only after Winnetou's death in "Winnetou III", the novel.)
Since Karl May had never originally planned to make the many different first-person-heros going either by the name of Charly, Charles, Old Shatterhand or no name at all to be actually one and the same person, the background stories vary from novel to novel. In the end, the editors from the “Karl-May-Verlag” decided to rewrite all of them according to Karl May’s last and most popular Old-Shatterhand-background stories in “Winnetou I”.
As for Old Surehand:
Originally, Karl May intended his novel “Old Surehand” to be another story about his second important white Western hero, Old Firehand. Old Firehand had been introduced in “Winnetou II” (the novel, not the movie) as a father figure for Old Shatterhand and Winnetou and reappeared in the novel “The treasure of the silver lake”. Since Karl May seldom ever re-read one of his own stories and being told of countless mistakes of continuity he had made during his former novels and rewrites, he decided to invent a new hero instead, so that new contradictions between his new novels and his old ones could not occur.
This new hero is “Old Surehand”. This Old Surehand is actually a half breed and brother to the half breed Apanatschka without knowing it. When he meets Old Shatterhand for the first time, he is some years older than him and already considered a famous scout. He mistakenly believes all his family scattered and killed. Mourning about them, he has lost his faith into god and become bitter and sad. With the help of Winnetou and Old Shatterhand he finds out about his brother. Finally, they even find their mother again who for a long time had assumed the disguise of an mysterious old Indian traveller and medicin man looking for her sons. Reunified with his surviving family members and having brought the bandit called “the general”, the murderer of his father to justice, he is able to find his faith into god again. This background story is told or rather found out about retrospectively only in the novel “Old Surehand”. It was never used for film. Stewart Granger worked only with the name of “Old Surehand” and a script which had originally been written for Lex Barker’s “Old Shatterhand”. Granger basically invented the film character all by his own. Few ever gave him credit for that since he behaved very divaesque and was not liked very well on the set. It is a pity that “Old Surehand” was never properly adapted, since the novel also contained a fascinating “otherworld-version” of Buffalo Bill Cody: Old Wabble, an old, dark, gruesome and brutal “doppelganger” of Surehand, Cody or any other “American” pioneer hero for that matter, a mixture of bragging old Sir John Falstaff, Old Rube and the Comedian/Edward Blake who kills buffalo and Native Americans for fun. In the movie, Old Wabble is just another Fuzzy-type character based on Gabby Hayes and Al St. John, though a sympathetic one.