To add to DJClayworth's excellent answer on the history of English translation, there has been a consistent and strong push to translate the Bible (especially the New Testament) into the vernacular see the very early days of Christianity. Below is a brief outline of the history of translation during the first millennium (minus English, which has already been well-covered)
Among the first Christian translations of the Bible is the Syriac language version, commonly known as the Peshitta. The general consensus among scholars is that work on the Peshitta in the second century as an Old Testament Translation. Following Bishop Rabbula's revision of the New Testament text in the fifth century, the Syrian Church (Nestorians and Jacobites) ordered a copy of the text placed in every church, making it the official scripture of the Church.
Although Greek remained the dominant language of the Roman empire until the third century, Latin translations began the appear already during the second century. Known collectively as the "Old Latin Version", there appear to have been at least two or three different Latin translations in circulation by the forth century, with many textual variants.
To combat the problem of variant versions, Pope Damascus ordered a fresh translation into the vernacular. Arguably the most successful translation ever made, the Latin Vulgate was translated from 382-204 by St. Jerome. The version was designed for common usage ("vulgate" means common), as "high Latin" was not well understood by the common people. Jerome's New Testament was an update of the Old Latin into the common language, while his Old Testament was a fresh translation from the original Hebrew (instead of the LXX as had previously been used.)
Egypt was one of the early pillars of the Christian church, so it is not surprising that vernacular translations were available from an early date. By the start of the fourth century, the New Testament had been translated into the Saidic dialect of Coptic. Old Testament translations appeared shortly thereafter, translated from the LXX. Further south, a Bohairic version of the Bible was developed in the following century. Its popularity eventually gave rise to Bohairic becoming the official dialect of the Coptic Church.
Although it is not clear when it initially arose, the Ethiopic version of the Old Testament appears to have been revised during the forth century, using the original Hebrew as the basis for its Old Testament. A New Testament translation was completed in the fifth century, possibly based on the Syriac version.
As Christianity spread into the Germanic region, the need for a local version of the Bible arose. According to church historians, the second bishop of the Ostrogoths, Ulfilas, invented an alphabet for the task bring writing to the tribe for the first time. Whether or not he actually invented the alphabet, he certainly made the first Gothic translation of the Old Testament (most books) and the New Testament, completing his work around 350. It is the oldest known literary work in any Germanic dialect.
During the ninth century, Charlemagne had the translation updated to the then-current vernacular dialect, Frankish.
The missionary effort of the Syrian church necessitated a translation of the Bible into Armenian. Like the Gothic version, church history suggests an alphabet was created specifically to make translation possible. An initial version of the New Testament was completed by St. Mesrob in the early fifth century. An Old Testament translation followed shortly after. A revised version on the New Testament based on the "best Greek manuscripts" was completed in the eighth century.
Christianity was brought to Georgia in the forth century and a Georgian translation of the entire Bible was commissioned in the fifth century, translated from the Armenian version. Like the Gothic and Armenian versions, an alphabet was developed specifically to enable Bible translation.
During the ninth century, the Moravian Empire rose to power in Eastern Europe. Rostislav, founder of the empire, ordered priests to conduct mass in the vernacular, necessitating a translation from the Latin Vulgate to Slavonic. To complete the task, the monks commissioned to make the translation created the Cyrillic alphabet. Due in large part to the success of their Bible translation, the Cyrillic alphabet superseded the existing Glagolithic alphabet and serves of the basis of modern Russian, Ukranian, Serbo-Crotian, and Bulgarian.
Summary of the situation in the year 1000
In the year 1000, most people who could read, could read Latin. It was the primary language spoken in southern Europe. For these people, the Latin Vulgate would be a perfectly accessible translation. In central Europe, a variety of Germanic translations of the Bible were available, including a recently updated version in Frankish. In England, multiple vernacular translations were available. In Eastern Europe, the Bible had been translated into Slavonic dialects, and in the South East translations were available in Syriac, Armenian, and Georgian.
In Africa, versions in Coptic and Ethopic were widely available.
Thus, most Europeans would have been able to hear the Psalms read in a dialect that they understood. Of course, few people could actually read the Psalms, since they could not read at all. But, yes, the message of the Psalms and the Bible in general was available to the common people of Europe, as well as parts of Africa.
Source: Most of the information in this post comes from From God to Us by Norman L. Geisler and William E. Nix.