[snowybeagle]

The use of homing pigeons (or sometimes known as messenger pigeons), or its relative the carrier pigeon, proliferate in wuxia novels.

However, was there any evidence of them (信鸽 or 飞鸽传书) used in ancient China?

[Yun]

Yes, I've found some in a book about the history of Chinese postal and messenging services.

Zhang Jiuling 张九龄, a famous Tang prime minister, reared pigeons at home. When he needed to send letters to his friends or relatives, he tied the letter to a pigeon's leg, and the pigeon would "deliver the letter to wherever he told it to go" (依所教之处飞往投之). Zhang called them "flying slaves" (feinu, 飞奴).
- This story is from the 《开元天宝遗事》

Yan Qingfu 颜清甫 of Qufu 曲阜 (in Shandong) was ill at home, and his son brought a pigeon down from the sky with a catapult and discovered a letter tied among its plumes. The letter was addressed from Mr Guo of Zhending 真定 (in Hebei) to his son Guo Yu 郭禹, the magistrate of Qufu. But by this time Guo Yu had been transferred to Pingyuan county 平远县, and because the pigeon did not know this, it kept circling above Qufu and thus got shot down by Yan's son. Yan quickly brought the letter and pigeon to Pingyuan and returned them to Guo Yu, who told him that the pigeon had been kept by the Guo family for 17 years, and it could send any family letter over any distance.
- This story is from 《玉芝堂谈荟》, which quoted it from 《百家风世传》

The Zhang Jiuling story popularized the term飞奴 for carrier pigeons, and it appeared again in two Song poems:

"飞奴解递丞相笺"
from 《问雁》 by Yao Mian 姚勉

"远欲飞奴传翰墨"
from 《寄周居安》 by Ouyang Che 欧阳澈

And also one Yuan poem:
肃肃其飞奴，离尔俦兮别尔家，
吁嗟尔劳兮，比鸿雁兮将书。
from 《义鸽》

There's also a similar case involving a wild goose (yan 雁) in the famous story of Su Wu 苏武, the Han envoy who was detained by the Xiongnu and sent to herd sheep at Lake Baikal. After peace was restored between the Han dynasty and the Xiongnu, the Han court asked for Su Wu to be released, but the Xiongnu lied that he was already dead. Chang Hui 常惠, a former attendant of Su Wu now serving the Xiongnu, secretly met the new Han envoy and advised him to tell the Xiongnu Chanyu 单于 (ruler) this story: the Han emperor was hunting in the imperial garden and shot down a wild goose. On the goose's leg was tied a length of silk on which was written "Su Wu and his men are now in such-and-such a place". The Chanyu believed this story and had to release Su Wu, suggesting that using birds to carry messages was not unheard of at the time.

[snowybeagle]

Uhm, I doubt if pigeons were ever that smart.

From what I understand, they could only find their way home, and some training is required.
Thus, they'd only be able to fly back to their perceived homes. Some accounts I read mentioned that they had to be trained/orientated to remember the route home.

[Yun]

Yes, there is surely an element of myth or legend in these stories. But they do illustrate that carrier pigeons were common enough.

[ih8eurocentrix]

In a documentry about mongol invasion of japan it said they used carrier pidgeon in correspondence with Khublai,ironically in Mameluke-Ilhkanids war book they say the mamelukes had faster communications becasue of the pidgeon carriers