Willy-nilly originally came from the phrase "will I, nill I", and variations thereof; "will he, nill he", "will ye, nill ye". Variations of this phrase have been around since the 1600s, and the Latin phrase of the same meaning, nolens, volens, has been around even longer. 'Will' in this case referred to desire or want, and 'nill' translates to something like 'to decline' or 'to be unwilling'. This would translate into modern English as "whether you want to or not".
""Marke mee what I say, Ile tell thee such a tale in shine eare, that thou shalt trust mee spite of thy teeth, furnish me with some money, wille, nille"
-- Thomas Middleton, A Trick to Catch the Old One, 1608
Hence the 'more correct' (e.g. original) definition of willy-nilly is "whether you like it or not". "You'll go to the store, willy-nilly".
Nowadays you are more likely to see it used to mean 'in a haphazard manner'. Books and clothes were strewn about willy-nilly". No one is really certain how this transformation came about. It probably originated as a misunderstanding of the original phrase, and spread because willy-nilly sounds like it should mean the same thing as helter-skelter and higgledy-piggledy.
I am always careful not to use willy-nilly in the second sense in writing, because it may very well annoy a pedant or purist. I also usually avoid using it in the original sense, because it confuses people. Pitty, it is a good phrase.