The pao in Chinese chess (xiangqi) is typically translated into English as cannon. However, the oldest known reference to the pao as a piece used in Chinese chess is from the Xuanguai lu, a Tang dynasty collection of ghost stories by Niu Sengru (779-847). This predates both the appearance of the first gunpowder recipe and the earliest representation of a cannon. The reason behind this apparent discrepancy is that the meaning of pao has actually changed over time. During the Tang dynasty, pao would have referred to a trebuchet.

Based on references to Warring States period trebuchets in excerpts from the Fan li bing fa (Art of War by Fan Li) and Mozi, the trebuchet has existed in China since at least the 5th century BC. The name pao becomes associated with the trebuchet in the early Han dynasty. The first recorded appearance of a game by the name of xiang, theorized to be an early ancestor of xiangqi, is from a description in the Zhou shu (History of the Northern Zhou) about an event that happened in the 6th century. The Zhou shu cites the Xiang jing (Classic of Xiang), but the text has not survived so we have no idea what the rules of xiang are or the types of chess pieces that were included. Therefore, it's chronically possible that the pao has always been a piece in Chinese chess, but references to xiangqi-like games prior to the 8th century are vague regarding the rules of the game and often dressed up in poetic language that is difficult to decipher.

Even in the Xuanguai lu, the pao is not explicitly mentioned as a chess piece. The story that involves chess is about Cen Shun, who is living in a dilapidated house isolated in the mountains. He repeatedly has a dream of witnessing a battle while aiding a general as a military advisor. Cen Shun grows sickly, and his relatives become worried that he is possessed, so they dig up the room where Cen is sleeping and discover a hidden tomb containing a Chinese chess set. While a pao chess piece never appears in the story, its existence is implied by the following passage:

Again the drums rolled, and on each side one infantry unit moved one square eastward and westward respectively. Again the drums boomed, and the chariots advanced. At this point, the drums gradually intensified, and each side brought forth bundles (of ammunition), (and then) arrows and stones flew back and forth.

The earliest mention of the pao that explicitly refers to it as a chess piece is in Qi guo xiangxi (Seven Kingdoms Chinese Chess) by Sima Guang (1019-1086) during the Song dynasty. This appearance of the pao is roughly contemporaneous with the development of the fire lance, an ancestor of the cannon and the firearm, but the pao mentioned in this text most likely corresponds to a trebuchet. Sima provides the earliest description of how the pao piece actually moves:

Each has one Catapult or Ballista (pao) which moves vertically or horizontally without limit on distance of travel. (However), there must be one intervening piece for it to be enabled to attack another unit. If there is no intervening piece (between it and its desired target), or if there are more than one intervening pieces, it may not attack.

Even after the invention of gunpowder, the use of pao remains ambiguous and can either refer to the type of projectile or the mechanism used to launch the projectile. Trebuchets that launched exploding gunpowder bombs are sometimes distinguished as huo pao (fire pao), but that name was also used in a pre-gunpowder context for incendiary projectiles. Metal-barrel cannons were invented in China during the 13th century, and are also referred to as huo pao. Later on, the stone radical in pao (砲) was replaced by the fire radical (炮) to differentiate gunpowder-based pao from earlier trebuchets. The character used for the pao chess piece was also replaced, but the piece retained its unique move of jumping over another piece.

For further reading:

Wang, Tzi-Cheng and Lo, Andrew. '"The Earthworms Tame the Dragon": The Game of Xiangqi"', Asian Games: The Art of Contest (2004): 168-179.

Chevedden, P. E., Shiller, Z., Gilbert, S. R., and Kagay, D. J. "The Traction Trebuchet: A Triumph of Four Civilizations", Viator, 31 (2000): 433-486.

Needham, Joseph and Yates, Robin. Science and Civilisation in China, Volume 5: Chemistry and Chemical Technology, Part 6: Military Technology: Missiles and Sieges. Cambridge: Cambridge University Press, 1994.

Andrade, Tonio. The Gunpowder Age: China, Military Innovation, and the Rise of the West in World History. Princeton: Princeton University Press, 2016.

Needham, Joseph. Science and Civilisation in China, Volume 5: Chemistry and Chemical Technology, Part 7: Military Technology, The Gunpowder Epic. Cambridge: Cambridge University Press, 1986.

Chase, Kenneth. Firearms: A Global History. Cambridge: Cambridge University Press, 2003.

The translations are from:

Leventhal, Dennis. The Chess of China. Taipei: Mei Ya, 1978.