Someone who does not settle in one place rarely prospers.
This proverb refers to what is well-known about mosses and lichens - that they are slow-growing organisms that don't thrive on disturbance. A sure way to prevent a colony of moss from growing on a stone is to move it about. As with all proverbs, it isn't the literal meaning that conveys the meaning but the metaphor. A rolling stone refers to a wanderer, unable to settle to any job or lifestyle and is therefore characterised as unreliable and unproductive.
That notion was known to the ancient world and Greek and Latin versions of the phrase are cited by Erasmus in the third volume of his collection of Latin proverbs - Adagia, 1508.
The proverb may have come into colloquial English before then, although early records are incomplete. We do know that it was known by 1546, when John Heywood published A dialogue conteinyng the nomber in effect of all the prouerbes in the Englishe tongue:
The rollyng stone neuer gatherth mosse.
Heywood's claim in the title to include all the proverbs in English is a little overstated, but Dialogue is the most comprehensive early collection and the source of many previously unrecorded proverbs. They were assembled from various sources, including Erasmus' Adages and from his own collecting amongst the Tudor populace.
By the early 17th century, a 'rolling stone' was referred to as a type of wastrel - one who would amount to nothing. In A dictionarie of the French and English tongues, 1611, Randle Cotgrave listed the French word 'rodeur' and gave it this definition in English:
Rodeur: A vagabond, roamer, wanderer, street-walker, highway-beater; a rolling stone, one that does nought but runne here and there, trot up and downe, rogue all the country over.
Quite a good name for a rock band you might think and Brian Jones thought just that when he formed to eponymous blues/rock band in 1962. Despite what appears to be Mick Jagger's impressively dogged attempt to sleep with most of the models in London and despite his long-standing friendship with Kate Moss, journalists have not had occasion to wheel out the inevitable headline 'Rolling Stone gathers Moss'.