What language would medieval Scots speak? Would it be like middle English, or did they have their own language? If so how close was it to English and were they even in the same language family?
There is no simple answer to this question, with Scotland being a country of remarkable (linguistic) diversity for much of its history and, though to a lesser extent, today.
For this answer, I will assume that by "medieval Scots" you mean the inhabitants of the medieval Kingdom of Scotland which existed from the 9th century until the union with England in 1707. For most of this period, the inhabitants of the Highlands were speaking Gaelic (Gàidhlig), while in the Lowlands Scots was spoken. Gaelic is a Goidelic language and was brought to large parts of Scotland by Irish settlers during the first millenium, displacing Brittonic languages such as Pictish. Brittonic and Goidelic are both subgroups of Insular Celtic.
However, the Gaelic sprachraum never covered the entirety of modern Scotland, with Cumbric, a Brittonic language, and Old English being spoken in southwestern and southeastern Scotland respectively and Scandinavian settlement on the Hebrides and in Caithness spreading Germanic (West Norse) in the 9th and 10th centuries.
As you can see, early medieval Scotland was a "melting pot", a diverse meeting ground for cultures that continually influenced each other. In subsequent centuries we can witness the development of Scots out of the Old English spoken in Lothian, which gradually spread to most of the Lowlands, whilst Gaelic consolidated in the Highlands and on the Hebrides, blending with the Norse or Norse-Gaelic communities there - though for example the Shetlands only became part of Scotland in 1469 and never spoke Gaelic.
As a result of these processes, we can say that in the High Middle Ages, Scotlands population would, mostly depending on the location (Highlands/Lowlands) speak either Gaelic or Scots as its native language.
Scottish chronicler John of Fordun, who lived in the fourteenth century, summarises this as follows (translation from Latin by Robert Bartlett):
The manners of the Scots vary according to their language, for they employ two languages, Scottish [G aelic] and Teutonic [Scots/English]. The race of Teutonic language has the sea coasts and lowlands, that of Scottish language inhabits the mountainou sareas and the outer isles. The race of the sea coasts is domesticated, civilized, faithful, patient, cultivated, decently dressed, refined and peaceable, devout in church worship, yet always ready to withstand any harm done by its enemies. The island or mountain race, however, is wild, untamed, primitive, intractable, inclined to plunder, leisure-loving, quick to learn, skilful, handsome in appearance but vilely dressed, and continually fiercely opposed to the English people and language, but also to their own nation, on account of the difference of language. Nevertheless they are loyal and obedient to the king and the kingdom, and also easily subdued to the laws, if they are ruled properly.
As Robert Bartlett writes, John considers both Scots- and Gaelic-speakers to be part of the same nation, though they are two races. So, in order to come back to your question: Medieval Scots would most likely speak either Scots or Gaelic (or both). Scots is in the same language family as English - Gaelic is not.
Bartlett, Robert: "Medieval and Modern Concepts of Race and Ethnicity". In: Journal of Medieval and Early Modern Studies, 31.1 (2001), p.47-51
Atina L.K. Nihtinen: "Scotland’ s Linguistic Past and Present: Paradoxes and Consequences". In: Studia Celtica Fennica II (2005).