Words are tricky beasts, aren't they? I mean, even a simple word that we all understand, like push, can mean advance or squeeze or tense certain muscles or political group or, simply, push-as-in-door.
It gets even trickier (and much, much sillier) when we insist on single meanings for complex, multipurpose words like anarchy, and all of the words made from that root, like anarchist.
One of the meanings of anarchy is, indeed, chaos. As in the opposite of order. But it would be a willfully ignorant (or irreparably stupid) person who assumed that what anarchists want, or what anarchism is about, was chaos. Kind of like the helpful husband in the joke who says "Push, darling!" and whose wife screams "Do you see any doors around here?!" In other words, while it may be effective ad hominem, it's just a joke to equate anarchism with chaos or disorder. This neatly dispenses with nearly 80% of the anecdotes-posing-as-intellectual-discussion that comprises the bulk of previous commentary here on the idea of an "anarchist army".
It is true, as the Oxford Companion to Philosophy puts it, that "there is no single defining position that all anarchists hold, and those considered anarchists at best share a certain family resemblance", which does make our quest for the anarchist army somewhat more difficult, but not insurmountably so. And while Wikipedia neatly summarizes as follows: "...some anarchist schools of thought differ fundamentally, supporting anything from extreme individualism to complete collectivism..." this divergence doesn't fundamentally alter the "family resemblance" the Oxford tome is talking about. Without getting too complicated, anarchists are basically agin' compulsion. Most commonly, this is an opposition to the compulsive powers aggregated by the state in all its various forms.
So an army that relies on a compulsory draft would not be an anarchist army. But of course most modern armies are volunteer armies -- professional soldiers who want to be there are obviously and provably better than cannon-fodder forced to fight -- and thus most modern armies are not by definition non-anarchist.
Likewise, there is nothing in anarchist philosophy which disallows hierarchy, so long as the hierarchy is not compulsory, and is agreed to by all. Anarchists of any stripe are not against specialization, which is all, at the end of the day, that the so-called military hierarchy is: strategy specialists co-ordinating the actions of the rifle specialists, supply specialists, artillery specialists, etc.
Very large groupings might prove a difficulty for an "anarchist" army, certainly the more individual-focused strains. Collectivist anarchism would have no such difficulty, but let's limit our notional "anarchist army" to small groups of like-minded volunteers just to be safe.
An implicit criticism of the anarchist army that's harder to shake is the idea that humans require the threat of punishment to be "good", or do things that the majority favours. This is harder to shake only in the sense that sizable majorities profess to actually believe this, usually stated in the form "if there was no God there would be no reason for anyone to be good". Pointing out the myriad counter-examples to this theory doesn't seem to have any dissuasive power: this is something that's simply believed. Likewise, elsewhere here we're treated to a version of this: if there was no military discipline (i.e. a regime of compulsory punitive punishment) people wouldn't be "good" (i.e. sacrifice themselves for the notional advancement of the army as a whole). Fortunately for the anarchist army, the specific military counter examples to this concept are simply too numerous to ignore or shrug off.
So what would an anarchist army look like? How effective would it be in combat?
Our limitations (as discussed above) are: volunteer, intelligent non-compulsory interaction between specialties, small groups, self-imposed discipline only.
Hey, wait a minute! That describes the SAS! Highly self-motivated volunteers, almost total lack of "military discipline", very robust interaction between specialties (including refusal of missions if individual squads feel they are planned on poor or incomplete intelligence), and, of course, utterly utterly lethal, and capable of taking on forces several times their physical manpower.
In case we get confused and try to limit words to one sense again, let me expand a little on "lack of military discipline". The SAS (and equivalent) certainly don't lack training in military disciplines like close-quarter combat, marksmanship, etc. But they do lack, and are famous for the lack of, the kind of spit-and-polish high-and-tight compulsory "discipline" that regular soldiers suffer under. Being able to perform all the "tasks of a soldier" to a high degree of proficiency requires no military discipline. It does, however, require a thoroughgoing knowledge of various disciplines that have traditionally been labeled "military". The fact that, in training, the SAS voluntarily accept tough discipline is neither an argument for, nor against, their "anarchy", but rather an argument which can be summarised with the old military catchphrase: "Train hard, fight easy."
And please don't take my word for the military effectiveness of such forces. Do a search for SAS or special forces. Even if just limited to conventional guerrilla warfare, the ability of exactly such forces to tie down, inflict asymmetric damage on, and eventually defeat "conventional" armies is well established.
One last point. Where would a notional anarchist army be deployed? Naturally, in defense of an anarchist society. And since one of the features of any anarchist society is that people are members because they want to be and are deeply, personally involved in the economic and political well-being of such a society, conventional notions of occupation, economic embargo, and military action against such societies simply don't apply. If war threatens, the entire society gets "behind" the soldier or citizen-soldier clade in such a way that a "conventional" state can only dream about.
To slightly paraphrase: if your society requires compulsion and brutal discipline for its "defense" then is it a society worth dying for? No soldier in any "anarchist army" would ever have that doubt.
POSTSCRIPT
It is possible to come up with a hypothetical tactical situation to defeat any theory of warfighting. Recently, for example, the manufacturers of the next-generation F-35 aircraft were dismayed to learn of a simulation where a swarm of 3rd generation fighter aircraft defeated a group of their highly advanced machines via the simple tactic of swarming the refueling tanker that is a key part of the F-35's air superiority capabilities.
Rather than point out that such a tactic would require suicidal dedication on the part of the enemy fighter pilots, the Pentagon and the manufacturers have chosen instead the time-honoured tactic of denying the validity of the simulation.
My point is that hypothetical battlegrounds with hypothetical force-balances which require the compulsory suicide of some fraction of the hypothetical "good guys" are obviously not the kind of situation where the New Model Anarchist Army excels. But why would an anarchist society choose to fight in that manner?
In fact, forget about anarchists, why would any sane society accept a geopolitical setup which required such compulsory sacrifices? For every hypothetical Fulda Gap there are, obviously, multiple winning tactical options which don't require compulsory suicidal "diversionary" tactics. And indeed if you read the history of the actual situation alluded to by DejaMorgana, many such tactical options were canvassed.
The fact that none of them were implemented says everything about how easy it was, having established compulsory suicide as a military "norm", to place forces in that configuration. But that's (clearly) an argument about society, not an argument about how wars should be fought, have been fought, and might be won.