As with so much in the Middle Ages, the answer depends on when and where. Famously, for instance, there are the Oaths of Strasbourg vowed in 842 between the sons of Louis the Pious, Charles the Bald and Louis the German, in their war against their stepbrother Lothar. The oaths survive in Latin, Old High German, and a very early French (Gallo-Romance). Louis swore his oath before his brother’s army in French; Charles swore before his brother’s army in Old High German so that the troops, many of whom were probably bilingual anyway, would understand them. Their grandfather, Charlemagne, was multi-lingual according to his biographer Einhard:
He was not satisfied with command of his native language merely, but gave attention to the study of foreign ones, and in particular was such a master of Latin that he could speak it as well as his native tongue; but he could understand Greek better than he could speak it.
By comparison, in England by the 13th century, members of the upper classes were usually proficient in their mother tongue, English, and French (Anglo-Norman). Walter of Bibblesworth wrote a French vocabulary in the mid-1200s to instruct a noble lady in proper French, not basic French, “which everyone knows.” Many of them, men and women alike, would also know at least rudimentary Latin, the language of government documents. So they would be trilingual. Those who lived and worked along the Welsh Marches would also likely know some Welsh. This kind of bilingualism can’t be assumed for the lower classes. There is the case of a bishop preaching to a Welsh congregation who had to have a friar translate for him. I can’t document this—I’m sure others can—but I’ve always suspected people of whatever class living along language borders probably had some basic bilingualism, much as people along the US southwestern border know some Spanish. It’s worth noting that there was incredible linguistic diversity all over Europe. In the Middle Ages “French” and “Italian” as we know them were only regional dialects centered around Paris and Florence respectively. Even in 19th-century France, people living just a few miles from each other might have a hard time understanding the neighboring dialect, as Graham Robb’s wonderful The Discovery of France: A Historical Geography notes.
That brings us to the clergy. Those with at least some education would be proficient in their mother tongue wherever they lived and in Latin, the language of learning. This is especially true of those men who had some university education where all the classes were taught in Latin. Still, at the University of Paris, for instance, students were divided into “nations” (French, Normans, Picards, English, Germans) according to the vernacular they spoke when not in class. Universities at Oxford, in Italy, Prague and elsewhere made their own national divisions. When the upper clergy assembled at international councils and synods, Latin would be their lingua franca, as it remained for centuries later in educated circles.
There was another true lingua franca in use around the Mediterranean among merchants. Sometimes called Sabir, it was a pidgin grab-bag with elements from several Romance languages, heavy on Italian and French.
EDIT: One more thought. In cosmopolitan places like Sicily or parts of Spain where several cultures came together, there are interesting examples of trilingualism, most famously the tombstone in Latin, Greek, and Arabic that the priest Grisandus put on his parents' grave in the late 12th century or the trilingual psalter compiled for King Roger (1130-54) of Sicily for use in a chapel served by both Greek and Latin rite priests with texts in Greek, Latin, and Arabic.
Sources: For English bilingualism I’m using Michael Clanchy’s classic From Memory to Written Record. I’m sure others among Ask Historians can provide much more detail than I offer here.