A question that I can finally answer!

There were many types of magic (or associated to it, such as inner alchemy, I will deal with it later in that answer) in ancient and medieval China, mostly associated with Taoism (magical practicioners were called fangshi), so I will probably not be completely exhaustive, I will just write down the elements that seem the most interesting to me (and mostly taoism, as I know the other types of magic a bit less, and I don't want to be lost in conjectures).

The most important one was divination, by taoist priests specialized in that. The first way to do divination that comes to mind is the Yi jing, one of the most ancient Chinese books that we still have today, that is used to foresee the future thanks to hexagrams, each made of trigrams, that are made following the theory of the yin and the yang. Without diving too much into the theory of the Yi Jing, it was used by virtually all Chinese aristocrats no matter their school of thought. Using sticks you make trigrams made of broken lines (yin) and unbroken lines (yang). Each trigram has a meaning. You then associate the two trigrams you obtained into a hexagram, that you interpret to see your future (Confucius made a very famous commentary of the hexagrams, so it is his commentary that was used by Confucianists). Another type, still linked with the yin and yang, but more used by taoists, was made by looking at the sky, the position of the celestial bodies being good or bad omen (for example x star being in y position while the z shape of moon meant a good omen, or a bad one). It could go as far as announcing the end of a dynasty (and that is why they were also used by the imperial household). There is also more shamanic magic, also linked with taoism, aimed at the control of the elements. One example is given to us in the Romance of the Three Kingdoms by Luo Ganzhong, that made Zhuge Liang use a ritual to control the wind, allowing him and Zhou Yu to defeat Cao Cao at the battle of Red Cliff. This event is fictitious, as no previous records of the Three Kingdoms narrated this event, but I think it is a good example of the types of magic that the Chinese believed in.

As for internal alchemy (called Neidan in Chinese) now, it is a taoist subject. The taoists believed that it was possible to reach immortality (immortals were called Xian), and to do that you needed a discipline. That involved meditation, a proper diet, proper sexual practices, a proper training, ... All aimed at controling the qi that flows through the body (it is the origin of many martial arts, such as the now popular Tai ji quan, or the infamous religion Falun Gong).

Another alchemy, called Weidan, also called "External Alchemy", that appeared earlier than Neidan, is aimed at fabricating elixirs, transmutating metals, ...

Talisman (fu) and incantations were also widespread, whether in Buddhist contexts or once again in a taoist context, used to protect yourself, fight demons, ... You can find some of these chants in the Zhougui Jing (used by the taoist group named "Celestial Masters"; I speak about this one in particular because it has been quoted in English in Introducing Daoism by Livia Kohn).

Sources:

• Introducing Daoism by Livia Kohn : very simple, but contains one small chapter about Neidan, a picture of a talism, and translation of two incantations.

• Taoist internal alchemy by the same Livia Kohn (she is a reference on this subject, so you can look at any of her books, they are usually very good)

• The way of the Golden Elixir, an Introduction to Taoist Alchemy by Fabrizio Pregadio

• Pratiques divinatoires, conjectures et critiques rationalistes à l'époque des royaumes combattants in Extrême-Orient, Extrême-Occident. 1999, N°21, pp. 67-77 by Jean Lévi. In French sadly, but a good synthesis of early Chinese divination, if you can speak French.

I didn't really refer to these books to write my message, so they are not to be considered as my sources, but if the subject interests you and you want to look further into it, I can recommend you:

• Tales of the taoist immortals, translated by Eva Wong. It is more literary, but it is interesting to see what it was to be a taoist immortal.

• The serie of 10 books Handbook for Daoist Practices, that are translations of ancient Taoist books by Louis Komjathy (but the first one is not a translation, just an introduction to the serie)

• All the books by Livia Kohn, most relevant here : Taoist Mystical Philosophy, The scripture of Western ascension

• The teachings and practices of the early Quanzhen Taoist Master by Stephen Eskildsen, dealing with the Quanzhen Taoist, that are one the biggest school of taoism, and had a strong mystical aspect.

Kegaha has a good answer here about some of the magical dimensions of Daoism, with some good sources. Augury was particularly important.

Early Chinese medicine also has strong magical elements to it. Cures in early medical texts often involve incantations or other methods to get rid of the spirits that are causing the illness. Donald Harper, who has produced some the best work on this, describes some of this medicine as 'magico-religious'. It's a bit academic for a lay reader, but he has a great chapter the Cambridge History of Ancient China and his own book Early Chinese Medical Literature.

Another incident that I think is fascinating and shows some of the interplay between 'magic' and other intellectual traditions was the Qing Dynasty soul sealing crisis. There is a great book by Philip Kuhn which gives an excellent narrative account of the events as well as an interesting discussion of the political ramifications and such. The quick version is that there were various superstitions in China about the way that a person's soul could be stolen, either by placing a slip of paper with the person's name on it under a bridge pylon or by cutting a lock of their hair. The soul could then be made to do your bidding, and the person whose soul had been stolen would become listless/suffer ill health. Folk religion and superstitions had, of course, existed for a long time, but during the Qing dynasty a number of soul stealing reports set off what was basically an inquisition. The Qing dynasty was ruled by ethnic outsiders, the Manchus, who came from what is now the far north east of China. They didn't really believe in this sort of superstition (not that they didn't have their own), but felt compelled to act on these soul stealing reports because people in the regions supposedly afflicted by soul stealing bandits were themselves starting to act out. Then too, for various reasons the soul stealers might have been seen as having a political agenda. The Manchus signified their conquest of China by forcing all Chinese people to adopt the Manchu haircut, which is the stereotypical shaved forehead and long pony tail. Cutting of the pony tail was seen as an act of cultural rebellion.

So, the Qianlong emperor did act, and various local officials rounded everyone up who was accused of being involved in soul stealing and tortured confessions out of them to try and find the black magic ringleaders. The campaign proved to be worthless, in no small part because so many had made false confessions to stop the torture.