Chinese naming is pretty straightforward: family name, then one or two characters chosen nearly at random. That's the short version.
There are a lot of family names (several hundred according to The Other Wiki), but a handful dominate: Zhang, Li, Wang, a couple dozen others. These are usually one syllable, though two syllable surnames do exist. Perhaps the most famous one is Zhuge, as in Zhuge Liang (and Sima, as in his rival Sima Yi) from the Romance of the Three Kingdoms.note A rather famous poem from the early Song Dynasty, the "Hundred Family Surnames" (百家姓 , Bǎijiāxìng), lists some five hundred surnames used at that time. The phrase "Bǎixìng" is also a conventional phrase for the people at large.
The most common surnames tend to be vary by region, with different names being more common in different provinces or countries. The most common Taiwanese surnames are Chen, Lin, and Huang. Historically, the Chinese used to have two surnames: a clan name (姓, xing) and a lineage name (氏, shi). In ancient China up to about the Zhou Dynasty, only men can use their lineage name as their surname; women have to use the clan name. E.g. famous poet Qu Yuan's clan name is Mi (芈); Qu (屈) is his lineage name. Over time, this distinction is blurred and eventually erased.
Generally speaking, any character(s) can be used for a given name, though families avoid repeating names or naming children after famous people. For most of the Imperial era, it was criminal to use the names, or the homophones of the names, of the current Emperor and all previous emperors of the same dynasty. In practice, names with bad sounds or unpropitious strokes and complicated or obscure characters are also avoided. While the given names can be just one or two random characters strung together, most parents tend to work in some auspicious meaning/symbolism. Those born during the Cultural Revolution, for example, tend to have given names with the character for "red", "people", "revolution", "army", "steel" and such revolutionary socialist concepts worked in somehow.
In some families, all the children of a generation will share one character in their name. Even if a particular generation did not actually do so, they may still be referred to as the '__ Generation' for genealogical purposes or for determining precedence and protocol at reunions. There is also a genealogical name ("pu ming", 谱名), which traditionally is what extended relatives of the family would have known a person by. In many cases, the "pu ming" of even famous people are obscure: the "pu ming" of Sun Yat-sen, Deng Xiaoping and Jiang Jieshi are "Deming", "Xiansheng" and "Zhoutai" respectively.
Chinese speakers generally do not refer to each other with first names only. In the Chinese subconsciousness, a name is a complete entity of mostly two or three characters, with the less-important first names following the important-last name like train carriages being pulled by the train engine. Casual references to others are generally Full-Name Basis. Formal references are more similar to western standards with last name + titles or titles only. When your character refers to others with their first names only, it is usually used to highlight a particular quirk of the character or a special relationship between the character and the person being referred to, usually closeness.
Nicknames are common, though the lack of common names means that there are no 'standard' nicknames like Tom for Thomas. Children are frequently called by one syllable repeated twicenote and people may receive other nicknames later in life. Most commonly, older men may be called "Lao (Last Name)" (Old ____), and younger men and women may be called "Xiao (Last Name)" (Little/Young ____).
Many Chinese figures are not generally referred to by name. Confucius and Sun Tzu are not names per se, but rather titles that are conventionally translated as 'Master Kong' and 'Master Sun.' Similarly, Lao Tzu is the Old Master.
Almost all famous historical figures you come across will have at least two or three names. Taking up art names ("hao", 号) were popular for public use while reserving their real names for intimates. In Romance of the Three Kingdoms (and in history), Zhuge Liang's art name is "Wolong" or "Fulong" ("Sleeping/Lying Dragon"). Each of them would have the given name ("ming"; 名), and then have a "zi" (字）, which is their courtesy/style name, used during more intimate occasions, and probably at least one "art name" (as mentioned above). This results in I Have Many Names, and they're usually used in the place of the given name (example: "Zhuge Kongming" note and "Zhao Zilong"). It should also be noted that back in those days, calling someone by their "ming" is considered extremely rude, and only reserved for use by one's parents or superiors (or anyone whom the person is very comfortable with); peers and friends addressed each other by their "zi". note To give another example, the Northern Song art polymath Su Shi ("Shi" being his "ming") is also known as "Su Dongpo" from his "hao" Dongpo Jushi (东坡居士, Householder of the Eastern Slope); his "zi" is "Zizhan".
More recently, Sun Yat-Sen is generally known in Chinese as Sun Zhongshan instead of his 'official' name used in family records. Yat-Sen itself is a romanization of the Cantonese pronunciation of the name his teacher gave him when he first went to school, while "Zhongshan" was a pseudonym adopted while in exile in Japan, where he took the surname Nakayama (read as Zhongshan in Chinese) from a sign on a palace near Hibiya Park in Tokyo. (His legal name is Sun Wen). On the other hand, Chiang Kai-shek is another name that passed into English via Cantonese— but that's not his legal name either; his legal name is Zhongzheng, adopted relatively late in his life; Kai-shek (Jieshi in Mandarin) is his style name. Gets even more confusing when Chiang Kai-Shek was born in Ningbo, Zhejiang province and so would have actually had his names read with the Wu dialect.
Amusingly, China's enormous and growing population has led to a number of problems, including one less well-known than most of the rest: not enough names. Chinese naming traditions mean that there are a fairly restricted number of possible names, and therefore a lot of people with the same name (rather like all the Joneses in Wales). As a result, younger Chinese people have developed a habit of giving themselves a nickname, often picked entirely at random, to distinguish from each other. There are a large number of Chinese kids called things like Wang "Harry" Xiao or Ling "Michael" (as in Jordan) Hui.
A practice particularly associated with Hong Kong and Chinese people in Britain is to combine a Chinese-format name with a Western forename put at the beginning, to give [Western personal name] [family name] [Chinese personal name]. An example American tropers may be familiar with is the actor Tony Leung Chiu-wai, who doesn't use his Chinese personal name in Roman-alphabet languages.