Во-первых, в каждом крупном городе были купеческие кварталы, где проживали иностранцы - это позволяло знакомиться с другими языками и культурами. Купцы, паломники, прочие путешественники подолгу проживали в других странах и перенимали язык, культуру.
Что касается изучения языков в том виде, к которому мы сейчас привыкли, в средние века так изучали латынь. Также, если говорить про Позднее Средневековье, к этому времени уже вполне сформировался институт дипломатии.
Более интересна ситуация, при которой правители и подданые порой говорили совсем на разных языках. В Швейцарии, которая образовалась в результате распада Священной Римской империи и вовсе проживают носители 4 языков.