The name of the rosary
To start with, English is decidedly unusual among European languages in having adopted the word bid, which essentially means a prayer or request, and transferring it to the small round object pierced with a hole. The English word “bead” for small round objects on a string, which dates from at least 1377 in this sense, comes from the Old English ebed, meaning “bid.”
The other languages of medieval Europe refer to beads of any material with words related to “pearl” (Dutch parels, German perlen, French perles, Swedish pärler, Italian perline or pallina), or “grain” (Spanish granos, Portuguese grânulos, Italian grano, German Korne). Russian calls them “balls,” Romanian calls them mărgea (“pearls”) or “globes,” and Greek has several words, most of which seem to mean something like “bubble.”
Comparative word origins are a fascinating study, full of little mysteries, though answers to "why" a certain word became the accepted usage are usually impossible to prove. English has its share of oddities: for instance, most other European languages call that wall-opening with glass in it by some version of the word fenestre, but in English it's a window, from the Norse vind-auge ("wind-eye"). All over Europe that four-legged friend of ours is called something like a hund, except in English, where it's a dog -- and no one seems to have a good idea where that one came from.
To get back to beads, however, traces of the earlier meaning of bid/bede as "a prayer" still remain. For instance, a wealthy patron in the Middle Ages may have supported poor bedesmen, who had promised to pray for the patron, and may have provided a bedehouse for bedesmen or bedeswomen to live in. Likewise, “bidding one’s bedes” in the Middle Ages does not so much mean praying with a literal string of beads, as it means praying for one’s bedes, that is, the people or requests one is obliged to pray for.
However, the expansion of the meaning of bede from the prayer to also include the object had already occurred by the time of Piers Plowman (c1377), who mentions someone with “... A peyre bedes in her hande And a boke vnder hire arme.” Incidentally, “a pair of beads” simply means a complete set, using an older meaning of the term “pair.”
As has been mentioned, this name for the string of beads, and for the practice of saying a series of Pater Nosters and Ave Marias, have both been derived from the Latin name of the prayer that begins, “Pater noster, qui es in caelis...” The use of this word to refer to the bead string dates from at least as early as 1250, and in a 1317 inventory we find mention of a paternoster of pearls. In Mandeville’s Travels (c. 1400), he mentions that “The Kynge...hathe abouten his Nekke 300 Perles oryent, gode and grete, and knotted, as Pater Nostres here of Amber.”
By further extension, anything that resembles beads on a string can suggest a paternoster, and so the word has been applied, for instance, to a string of lakes by geologists (paternoster lakes), or to a variety of mechanical devices that operate like an endless wheel or string of buckets. (For more on this, see here.)
The word “rosary” originally meant a garden devoted to the growing of roses (c1440, “This mone is eke rosaries to make, with setes [seats]”). Chaucer also cites Rosarium Philosophorum in 1386 as the title of a treatise on alchemy by Arnaldus de Villa Nova. Probably both the rose-garden concept and the book title contributed to the idea of referring to a collection of written prayers and devotions as a (metaphorical) rosary, such as the 1526 Rosary of Our Savyour Jesu or the 1533 Mystik sweet Rosary of the faytheful soule.
From here it was a short step to applying the term “rosary” to the specific prayer practice we have been discussing, including its string of beads.
Other European languages also call the rosary by a name referring to roses. In German it is a rosenkranz, in French a rosaire, in Italian and Spanish a rosario, and in Hungarian it is a rózsafüzért (literally a “rose string”). However in Austria it is more commonly a betschnur (“prayer string”) and in France, often a chapelet.
This was also probably encouraged by a secondary meaning of “rosary” as a wreath or chaplet of roses. A popular legend of the time helped to spread this metaphor widely (if you're familiar with the Paternoster-row website you've already heard this one).
In the legend, bystanders — actually robbers! — saw a young monk, stopping to rest in his journey, kneel down in the road and begin reciting “Ave, Maria...” As each prayer dropped from the monk’s lips, it turned into a rose, which was gathered up by the Virgin Mary standing nearby (the monk evidently didn’t see her, but the robbers did). The Virgin showed her pleasure at the gift of prayers by weaving the roses into a garland for her head. And since this is a legend, of course, the story adds that the robbers immediately repented and hastened to a priest to confess their sins, became monks, and died a holy death in the best legendary style!