The origin of this story seems to be with the translator of a manuscript found in the library of Trinity College, Cambridge. The manuscript is a poetic treatise sent by Queen Philippa's mother, the Countess of Hainault, about rosemary's many uses. Presumably it was sent with a rosemary plant, and thus the legend of the introduction of rosemary to England was born. The treatise has such useful advice as:
mighteth the boones and causeth goode and gladeth and lighteth all men that use it. The leves layde under the heade whanne a man slepes, it doth away evell spirites and suffereth not to dreeme fowle dremes ne to be afeade. But he must be out of deedely synne for it is an holy tree.
Strengthens the bones and causes good, and gladdens and lightens all men that use it. The leaves, laid under the head when a man sleeps, do away with evil spirits, and will not allow one to dream foul dreams or be afraid. But he must not be in a state of sin, for it is a holy tree.So was it known in England before the 14th century?
The British Library has a manuscript (Royal 12, D xvii) known colloquially as "Bald's Leechbook,"* a ninth-century medical text written in Old English. Rosemary is mentioned in a number of remedies, for fever, horses leprosy, and toothache (always mixed with multiple other substances). It is highly likely that the Saxons found rosemary growing all over England because of its introduction by the Romans centuries earlier.
*Bald's Leechbook deserves its own entry or three. [Update: here it is.]