One modern meaning of this common but odd-looking expression is “without direction or planning; haphazardly”:
We've got to make it a physical game and we are not going to go there and chuck the ball about willy-nilly. We've got to go there with a purpose and that purpose is to win the game.
Doncaster Free Press, 15 Nob. 2011.
Its original sense appeared at the beginning of the seventeenth century, when people used it to suggest that something must be done no matter whether one is willing or unwilling, whether one wants to or not. It’s a modified form of an older phrase that is variously expressed as will I, nill I or will ye, nill ye, or sometimes as nilling willing.
Will here is used in its sense of wanting to do something, to wish or desire that something should happen (when you make your will, you are using the same sense: you are expressing your wishes for the distribution of your goods after you die). Nill is very old, known before the Norman Conquest, but has long since vanished from the language. It was the opposite of will, so to nill is to want not to do something, to refuse or reject some course of action.
So will I, nill I can be expanded into “be I willing, be I unwilling”, combining the two sentiments with the implication that it doesn’t much matter what you feel, you’re stuck with doing something. More recently, this conflict gave rise to an implication that a person was not sure whether to do something, and so suggested he was undecided or indecisive. Even more recently, the associated sense has grown up of embarking on some project without direction or planning or in a disorganised way.
There is an equivalent Latin phrase nolens volens, which is formed from two Latin participles that mean “unwilling, willing”. It is sometimes said that willy-nilly is actually a translation of the Latin phrase. It may have been an influence, but it’s hard to tell.