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 long, 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.note The phrase "Bǎixìng" (百姓; lit. "Hundred Surnames") 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 (姓, xìng) and a lineage name (氏, shì). 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 (i.e. by around the Han dynasty), this distinction is blurred and eventually erased. Another thing to note for pre-Qin Chinese names is that famous personalities are sometimes addressed by putting their courtesy/style name (字; zì) first, followed by their given name (名; míng), leaving out their xing and shi completely. For example, Confucius's father is referred to as Shuliang He (叔梁紇) in records; "Shuliang" is his zi, while "He" is his ming.note By tradition, the child is given their zi at their coming-of-age ceremony. For gents, this is the guan ceremony, usually held at the age of 20 or slightly earlier; ladies have their ji ceremony at the age of 15.note
Almost all famous historical figures you come across will have at least two or three names. Taking up art names (號/号; hào) 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 ming, and then have a zi, 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 (except if the person is referring to themselves in the third person) is considered extremely rude, and only reserved for use by one's parents, superiors, or anyone whom the person is very comfortable with; peers and friends addressed each other by their zi, while people addressed their superiors by their hao.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".
For emperors, empresses and officials, there is an additional posthumous name (諡號/谥号, shìhào). A posthumous name is meant to encapsulate the deeds and reputation of the emperor/empress/official. Emperors of the Han and Sui Dynasties were primarily known by their posthumous names; Liu Che's posthumous name was "Emperor Wu of Han" (漢武帝/汉武帝, Hàn Wǔdì), while Yang Jian's was "Emperor Wen of Sui" (隋文帝, Suí Wéndì). However, as later dynasties became more pompous and lengthened their emperors'/empresses' posthumous names to ridiculous levels (Nurhaci's posthumous name is more than 20 characters long), their emperors became known by their temple names (廟號/庙号, miàohào). Note that emperors commonly known by their posthumous names also have temple names. (The temple name of each monarch was recorded on their respective ancestral tablet placed within the grand temple built for ancestor worship.) In the examples above, Liu Che's temple name was "Shìzōng" (世宗), while Yang Jian's was "Gāozǔ" (高祖). As a general rule of thumb, if the name used has dì (帝) in it, chances are it's the posthumous name; if the name has zǔ (祖) or zōng (宗) in it, it's likely to be the temple name. In addition, Ming and Qing emperors are also known by their era names (年號/年号, niánhào) as each emperor from the two dynasties used only one era name for their entire reign; the exception was Ming Yingzong Zhu Qizhen, who had two separate reigns (with era names "Zhengtong" and "Tianshun") and so is primarily known by his temple name.
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 (violating the "naming taboo"). 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.note
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 (譜名/谱名; pǔmíng), which traditionally is what extended relatives of the family would have known a person by. In many cases, the puming of even famous people are obscure: the puming of Sun Yat-sen, Deng Xiaoping and Jiang Jieshi (Chiang Kai-shek) 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 ____). Another common diminutive prefix to denote familiarity is "Ā" or "Ah" (阿), but it's mostly used by Southerners (and their descendants) rather than Northerners, so this is more likely to be heard in Hong Kong, Macau, or Taiwan (which has a lot of cultural influence from the southeastern Fujian Province) than say, Beijing.
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.
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, or ming, 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 (ming) either; his legal name is "Zhongzheng", adopted relatively late in his life; "Kai-shek" ("Jieshi" in Mandarin) is his style name. It gets even more confusing when Chiang Kai-Shek was born in Ningbo, Zhejiang province, and so would have actually had his names read with one of the Wu dialects.
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. These nicknames are often English or otherwise Western names in the face of globalization, sometimes used for the convenience of Westerners or to assert their individuality, among other reasons. For example, there are a large number of Chinese kids called things like Wang "Harry" Xiao or Ling "Michael" (as in Jordan) Hui. However, some of these nicknames can also sound like Real Joke Names, oftentimes being unusual word names, as it may just be a direct translation of the person's Chinese given name or, as above, a way to assert their individuality.
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.