So I know you don't likely mean Korea when you say Middle Ages. But let's pretend!

In the 15th century, it would not have been uncommon for Korean nobility to try to learn Chinese. Not Classical Chinese, which is something they would have learned anyway, but actual spoken Chinese (which differed greatly).

The usual answer to the question of "how did people learn languages a long time ago if there weren't books" doesn't apply in this case, because at that point in time, there were books. Specifically, there was the Nogeoldae (老乞大). While not the only text out there, the Nogeoldae is one of the most well known, and for good reason. It was a text designed to assist Korean speakers in learning Chinese. Which is great for me, a Chinese historical linguist, because from it we can learn all sorts of things about how Early Mandarin used to be. With Chinese languages, we have a good understanding of what the situation was during the Tang era, and we know obviously what the situation is now, but we don't have a good tree model for how the Sinitic languages relate to each other. The Nogeoldae helps with that, though.

Perhaps the most interesting part of the text from the perspective of a language learner is that it looks basically exactly like what today's language learning books look like. It's primarily based on simple conversations of the guy from the learner's country going to the country of the language being learned.

Click here to see the first page which I'll transcribe a bit here to explain.

Reading top to bottom starting on the second column from the right (the first column being the text's name), the Chinese characters reads 大哥伱從哪裏來, "older brother, where do you come from?", a sentence any modern-day Mandarin speaker will understand. Below each character you see two syllables written in hangeul, one showing an older pronunciation and one showing a more modern pronunciation.

It's a fantastic text because it was maintained and updated for centuries. Later editions had Manchu and Mongolian text, and different versions also had varying forms of colloquial Korean, making it invaluable for a wide range of historical linguistic endeavours.

How the language was learned would resemble what you do today. You'd have someone walking you through the text, practicing the dialogues, working out the grammar. It's not something a peasant would have necessarily done, however remember that at this period, civil service exams were how you improved your position in life, and those were heavily based on literacy and your ability to handle classical texts. Beyond that, there's always been a long history of Koreans living in China as merchants, so there's no real reason why someone of low status wouldn't ever learn another language, especially Chinese.

The only other thing I'd add is actually regarding Chinese peasants in China: Any sort of success in life in the form of government appointments would mean you need to be able to speak the lingua franca, so in that regard, having to learn another language would be quite a bit more common, especially for those aspiring to pass the civil service exams. But in this case it would be that they were learning the national language, rather than that of a far off kingdom. Still no small feat, but perhaps less exotic sounding to some of the readers here.