The ordinary people would not likely have come into contact with those from outside their area, unless in a market of some sort. But the upper nobility/kings, etc would have had some contact, for example the Northumbrian kings in alliances with the Gaels/Picts or the Welsh with the Mercians. How would they communicate? Was it simply a matter of being bi-or tri-lingual? Or seeing that many of the upper classes, if they were educated, would have been through the monasteries, so would they use Latin as a common language? Even the Welsh/Irish had different forms of Gaelic, as I understand, but could they understand each other when they spoke to each other?
The short answer is that there was no universal lingua franca. The Welsh did not (and do not) speak a form of Gaelic. (Irish) Gaelic and Welsh are both Celtic languages, but they belong to two different subdivisions sharing a common ancestor. Welsh is p-Celtic, or Gallo-Brittonic, while Irish (and Scots and Manx Gaelic) is q-Celtic, or Goidelic. They are not mutually understandable, so no, a monoglot Welshman could not speak with a monoglot Irishman and be understood. There was also another Celtic language spoken in Britain at the time whose exact placement in the Celtic family is somewhat disputed but which seems to have been more closely related to Welsh, namely Pictish, spoken in the North and in Scotland. The 2000 edition of Glanville's Languages in Britain and Ireland is a great overview of the different languages spoken and their relationships.
Diplomatic communications, like charters, letters, and treatises, were mostly conducted in Latin, sometimes in Old English (within and between English territories). Latin was mostly a written language. Communications between monarchs would have been done with the aid of interpreters and diplomats.
Multilingualism seems to have been common, though because of the nature of the historical record it's hard to know how much the "average" person knew, and the answer would depend on where they lived anyway. King Oswald of Northumbria lived in Ireland for a while and spoke the language; Bede writes that he helped an Irish bishop with his English. Saint Guthlac, per his Vita, knew English, Latin, and "British" (Welsh).
English was, unsurprisingly, very widely used in most of what is now England as it was the language of prestige, being the tongue of the Anglo-Saxon ruling class. /u/hoerensagen has recently given a very good answer on how Celtic speakers learned and changed the English language, which may be helpful for your question.