The victor of the Warring States, Qin Shi Huang, was famous for being the person who truly "unified" China by dictating that the whole country must use the same width gauge for carts (and therefore roads), and the same script for language. This enabled the centralised bureaucracy which he envisioned. Naturally, that means that before him, each region would speak their individual dialects. Note that he unified the writing, not the spoken language, which is why, even to this day, China is host to dozens of different dialects which all share the same writing system, but are almost as different as Western European languages are from each other. The most familiar example would be Cantonese, which is as understandable to a speaker of Mandarin as French would be to a speaker of English, even while the writing is 95% identical.

To anticipate follow-up questions, the Qin dynasty script is almost still readable by modern Chinese speakers. They look archaic and weird compared with modern script (left), but one could still make out some characters that have survived 2500 years nearly unchanged.

It follows that during the Three Kingdoms and Northern and Southern States periods, the script was already unified, and therefore any piece of writing could be read across the length and breadth of China. I am not completely familiar with the spoken dialect during those times, but there would be a dominant 官話 (guan hua, "official speak") spoken in the capital and by officials, which changed with the dynasties who liked to move the capital around a lot. Modern Mandarin is technically a northern dialect favoured by the Manchus of the last dynasty, Qing.

Sorry if this is a rambling answer, since I'm not specifically a linguistic expert, but have studied Chinese history a fair deal and pieced together this reply from bits and pieces of what I know.

I think you'll find this article interesting:

"Vernacular Languages in the Medieval Jiankang Empire"

http://sino-platonic.org/complete/spp250_jiankang_empire.pdf

It goes into the different spoken Sinitic languages of the Southern Dynasties:

The most prestigious was that spoken by the literate elite at the capital, Jiankang, which descended from the language spoken around 4th century Luoyang and had been carried south by the elite families fleeing the chaos of that era. This was consider by them as the proper way to speak. By the end of the Northern and Southern period this language/dialect had apparently diverged sufficiently from that in the north that northerners could be mocked for their uncivilized speech:

"At that time among Ru scholars who had come from the north there was Cui Ling’en, Sun Xiang, and Jiang Xian; they all assembled disciples and gave lectures, but their nunciation and phrases were crude and clumsy; only Guang’s speech and arguments were pure and ya, not like a northern person."

The northerners didn't have much good to say about the southerners either:

"Although Qin urvivors and Han convicts mixed in using some civilized speech, nonetheless the difficult languages of Min and Chu cannot be changed"

"The officials of the central plains exclaim that Jiangdong people (i.e., the southerners) are all acting like badgers, and said they were akin to foxes and badgers. As for the Ba, Shu, Man, Liao, Xi, Li, Chu, and Yue [peoples]: their languages are as dissimilar as the sounds of birds and the cries of fowl, their preferences all as different as those of monkeys, snakes, fish, and turtles."

Wu language originated as a blend of Sinitic and the native languages of the Wu and Yue states of the Spring and Autumn era. This was the native speech of the Jiangdong era, including the native southern elites, and was the language spoken at the Wu court during the Three Kingdoms era (the Sun clan were themselves natives of Wu) As such it also enjoyed a certain prestige.

Another spoken language was that of Chu (here Chu is used in a late Warring State sense, i.e. the Huai region) As quoted above it was considered by northerners as quite barbaric and bird-like, possibly due to having more tones than northern languages. To them this was a language of country bumpkins, but these bumpkins included most of the soldiers and generals in the South's Northern Headquarters army, including the founders of the Liu Song and Southern Qi dynasties.

There were many other dialects and languages as well, but evidence these are much more slim

During the Warring States the large southern state of Chu spoke a non-sinic language. (https://www.umass.edu/wsp/resources/chu/lexicon.html) The other Zhou states spoke a form of Chinese with no obvious dialectical differences. I don't know about later dynasties but I assume that in the Northern and Southern dynasties the north received influences from Steppe languages and the literate elites of the South spoke (good, proper) Chinese.