It is hard to trace back the very first flying sword in Chinese mythology or literary history, but I might try to give a list of what I could find.
In Chinese characters, "flying sword" is written as "飞剑". Searching this keyword on http://corpus.zhonghuayuwen.org/ACindex.aspx, we can get some examples:
Liu Jingshu (around AD450), a government official at The Southern Dynasties, written a story collection named The Garden of Marvels(异苑).
It recorded a story: The sword used by the first Han emperor Liu Bang was lost in a fire, however, bodyguards reported that the sword jumped through the warehouse and flew away itself.
A History book written during the Tang Dynasty (around AD600), named "Book of Jin Dynasty", record a story about a scholar named ZhangHua. ZhangHua's friend has a sword and passes it to his son. One day his son carries this sword passing through a river, this sword abandons him, jumps into the river, transforms into a Chinese dragon, then flies away.
Lu Dongbin (around AD800), a Taoist priest of the Tang Dynasty, written a poem: "得道年来八百秋,不曾飞剑取人头。玉皇未有天符至,且货乌金混世流。" I try to translate it into English: "Since I become immortal, hundreds of years past; Never did I chop an evil's head by my flying sword; The Jade Emperor did not summon me with his heaven's order; I would rather live on the earth as a trader selling mysterious gold". However, it is hard to prove whether or not this poem is really written by him. Lu Dongbin is deified as a god by people in the later dynasties. He often appears as a "flying sword" user in novels of Ming or Qing Dynasty. There is a novel from Lasting Words to Awaken the World(醒世恒言) named "Lu Dongbin flys his sword to slash HuangLong". It is about how Lu Dongbin, a Taoist priest, is defeated by a Buddhist named HuangLong. You can read this story at http://www.xiexingcun.com/3y2p/03/mydoc023.htm (Chinese characters warning!). Lasting Words to Awaken the World is written around AD1600 (Ming Dynasty).
As mentioned by @MorrisonChang, in Journey to the West, there is a very short episode about Sha Wujing being punished by flying swords. Journey to the West was written in Ming Dynasty by WuChengeng (around AD1500). At Ming Dynasty, "flying sword" had become popular and appeared in many novels, such as "Investiture of the Gods(封神演义)", "The Romance of Three Kingdoms(三国演义)". However, at this time, "flying sword" only "made a guest appearance" and is usually not the highlight of the story.
I believe the first "orthodox", and the most famous "xianxia" novel, should be "The Story of a Swordsman from Shushan(蜀山剑侠传)" written by Li ShouMing (AD1932). It is a long story about good and evil celestial beings fighting each other. "flying swords" are often their most important weapon and appear as a highlight in the title: Swordsman means the celestial beings who use "flying sword".