Scarborough Fair is a folk song which dates back to at least the 17th century. Folk songs were, as the name suggests, passed on by oral tradition and relatively little was written about them until music scholars began to take an interest in them in the late Victorian era. As such, the origins and meanings of these songs are often lost to history, and we cannot make definitive conclusions about them.
We can, however, make a game attempt at tracing the origins of this song, which may shed some light on its meaning. As an oral tradition, folk songs were very often adapted and changed by different performers, and there are clear relationships between very many of them. The motif of impossible tasks is not rare: it can be found in songs such as Unquiet Grave:
Go fetch me a note from the dungeon so deep
Fetch water from a stone
Or milk white out of a fair maid’s breast
When a fair maid never had none.
Or Acre of Land (note that an acre of land is also referred to in Scarborough Fair):
I sent it home in a walnut shell;
I threshed it with my needle and thread.
I winnowed it with my handkerchief;
I sent it to mill with a team of great rats.
But these do not seem to be related to Scarborough Fair. Rather, its origin appears to be a song called The Elfin Knight, in which a woman is propositioned by an elf, a supernatural being. In some versions, the elf is threatening to rape the woman, in others she is seeking him willingly. Either way, the elf responds by setting the woman a very similar series of tasks to gain/avoid the liaison:
O fetch to me aye a Holland shirt,
Aye thout either needle or needle work.
For you’ll fetch to me two acres of land
Between thon salt sea and thon salt sea strand.
And so on. In this instance, it seems reasonable to assume that these tasks exist to highlight the magical nature of the elfin being. Songs involving elves performing supernatural feats are, again, common in the folk song canon: Tam Lin is a particularly famous example. This creates a great deal of dramatic tension in the narrative, separating the otherworldly elf from his mortal lover and raising the stakes with each passing impossibility. Of particular note is the fact that the supernatural element suggests that these tasks are not impossible for the elf.
In Scarborough Fair, the protagonist is now presumed to be a mortal man instead, but the impossible tasks remain. In this context, it would seem that the tasks are designed to test just how much the woman loves the man: is she so desirous of him, in other words, that she is willing to attempt the impossible to woo him?
This ties in to the repeated statement that "she once was a true love of mine". The implication here is, of course, that the lady is no longer the singer's true love, possibly because she committed some act of betrayal. So hurt is the singer by that act that he is now demanding an impossible task to prove that she is worthy to win back his love - "then she'll be a true love of mine".
Either way, divorced from the supernatural elements of the previous song, the tasks seem somewhat bizarre to the modern listener. It's possible that the refrain "Parsley, sage, rosemary and thyme" is a distant echo of this supernatural origin. Sage as a folk medicine was seen as a way to ward off evil: elves, as ungodly beings, would have been seen as Satanic in the era in which the song originated. Thyme was similarly used to ward off nightmares. Rosemary, meanwhile, is both a love charm and a commemoration of death, and there may be a relationship with the impossible tasks set by the ghost in Unquiet Grave.
This is often the way with folk songs: over the centuries of oral traditions, important parts of the narrative get lost and what remains does not entirely make sense. Horkstow Grange is an old song from which famous folk-rock band Steeleye Span got their name, and it's clearly about a quarrel between two workmen. However, the reasons for their quarrel and the denouement of the incident are lost. It may be that Scarborough Fair originally included more overt links to the supernatural, which have not been recorded for modern listeners.
cough