A morris dance, or the boy in the morris dance, called Mad Morion, from the “morion” which he wore on his head. (See Morris Dance.) Maid Marian is a corruption first of the words, and then of the sex. Having got the words Maid Marian, etymologists have puzzled out a suitable character in Matilda, the daughter of Fitz-Walter, baron of Bayard and Dunmow, who eloped with Robert Fitz-Ooth, the outlaw, and lived with him in Sherwood Forest. Some refine upon this tale, and affirm that Matilda was married to the outlaw (commonly called Robin Hood) by Friar Tuck.
“A set of morrice dancers danced a maidmarian with a tabor and pipe.” —Temple.
Next 'tis agreed That fair Matilda henceforth change her name, And while [she lives] in Shirewodde ... She by maid Marian's name be only called.
Downfall of Robert; Earl of Huntingdon.
Source: Dictionary of Phrase and Fable, E. Cobham Brewer, 1894
More on Maid Marian from Fact Monster: