This term has two, slightly differing, but related meanings: 'whether it is with or against your will' and 'in an unplanned, haphazard fashion'. We tend to use the latter of these meanings today; the former was the accepted meaning when the term was first coined.
There are many spellings in early citations, which relate to the 'with or against your will' meaning of the phrase - 'wille we, nelle we', 'will he, nill he', 'will I, nill I', etc. The expression also appears later as 'nilly willy' or 'willing, nilling', or even, in a later humourous version 'william nilliam'. The early meaning of the word nill is key to this. In early English nill was the opposite of will a contraction of 'ne will'. That is, will meant to want to do something, nill meant to want to avoid it. So, combining the willy - 'I am willing' and nilly - 'I am unwilling' expresses the idea that it doesn't matter to me one way or the other.
The Latin phrase 'nolens, volens' means the same thing, although it isn't clear whether the English version is a simple translation of that.
The second, 'in an undecided, haphazard manner', meaning of willy-nilly arrives from the first. The changeable 'this way, then that way' imagery of willy-nilly behaviour fits with our current 'haphazard' meaning of the term.
There's also a, now archaic, phrase 'hitty missy' that had a similar derivation. That comes from 'hit he, miss he'.
The phrase dates back at least a millennium, with the earliest known version being the Old English text, Aelfric's Lives of Saints, circa 1000:
"Forean the we synd synfulle and sceolan beon eadmode, wille we, nelle we."
Shakespeare was familiar with, and apparently quite fond of, the expression in various forms. He used it in The Taming of the Shrew, 1596:
Petruchio: [To Katharina]
Thus in plain terms: your father hath consented
That you shall be my wife; your dowry 'greed on;
And, Will you, nill you, I will marry you.
[that is, I will marry you, whether you like it or not.]
and again, in Hamlet:
First Clown: Give me leave. Here lies the water; good: here stands the man; good; if the man go to this water, and drown himself, it is, will he, nill he, he goes.
[that is, If a man chooses to drown he enters the water, if he chooses not, he leaves.]
The 'undecided' meaning of the expression appears to have spawned the later 'shilly-shally'. The OED is a little lax in dating this from the end of the 19th century. They cite Sir Walter Besant's novel The Orange Girl, 1898:
"Let us have no more shilly shally, willy nilly talk."
That makes the connection between 'willy-nilly' and 'shilly-shally' apparent. There are literally thousands of 18th and 19th century pre-datings of the phrase, in various newspapers and works of literature; for example, The Adventures of Dick Hazard, 1755:
Where I quartered, a good buxom Widow kept the house; and I had her before I was ten days in town --D-- me. She knew things better than to stand Shilly Shally.
See other reduplicated phrases.