In China, the surnames come from various sources.
The first original surnames came from the rivers by which the emperor lived. At that time, surnames were used to distinguish between tribes. Therefore the follows of the Yellow Emperor 黄帝 took on the surname Ji 姬 because he was born near Ji river 姬水, while the followers of Yan Emperor 炎帝 used the surname Jiang 姜 because he lived by Jiang river 姜水.
With time surnames changed from being labels for a tribe to representing a single bloodline. Other than those that were passed down from parent to child, people began using other influences to give themselves surnames.
Locations were the most common inspiration for surnames. The various states during the spring autumn/warring states period all became used as surnames soon after (e.g Lu 鲁, Yue 越, Zhao 赵, Chu 楚). The lands gifted to a subject may also become his surname, like how the Xun Ying 荀罃 changed his surname to Zhi 智 based on his uncle's fief. Others took the literal position they were in to be surnames, just as a family living near the West gate of the Zheng 郑 state took the surname Ximen 西门 (meaning west gate).
Another source of surnames were ancestors. The descendants of Ji Linkai 姬林开, son of Ping king of Zhou 周平王, took the first word of his name as a surname Lin 林. Likewise, the grandson of Song Chongshi 宋充石 used his courtesy name Huangfu 皇父 as a double-barreled surname.
And the other most common source of surnames would be from occupations. The Sima 司马 family took their surname from the post of sima, a military position somewhat corresponding to that of a marshal. And the surnames Pu 卜 and Tu 屠 came from the occupations of a fortune teller and butcher respectively.