(I can't remember if I'm promised this before or not. Anyway, I've just cleaned it up, added some references and so on. So, here you go.)
I won't bother explaining what primitivism is here, I assume you already know what it is (at least the basics). Instead, what I intend to do here is show that while some primitivists might "legitimately" (and I quote this because I know that there are numerous other anarchists who would refute the claim that any primitivist could be an anarchist, but allow me to explain) claim the title "anarchist", others most definitely can't.
Anarcho-primitivists are those primitivists who have an anarchist critique of civilisation (no matter how incorrect you may think it is), and thus come to the conclusion that, for an and to domination, oppression, hierarchy etc. (all those things that anarchists want to bring to an end), and the creation of a free society (etc. see previous parentheses), civilisation itself must be brought to an end.
Now that I've brought that term (civilisation) into the matter, I guess I should explain what I mean... There are a number of different definitions around the place. These range in scope and effect, from simply discussing modern society, to going in-depth into the development of writing and "complex political and social institutions" http://www.answers.com/civilization (accessed 19/02/2007). One anarchist definition describes civilisation as "a network of institutions, structures and systems that impose social relationships of dominations and exploitation" http://www.geocities.com/kk_abacus/vb/wd3-3civil.html (accessed 19/02/2007). Because definitions vary such a lot, you should check the meaning of terms before condemning people based on labels... (See also the piece Anti-civilisation? Whatever do you mean? http://old.revleft.com/index.php?act=blog&id=5004 .)
Then, there is another sort of primitivists. These are the environmental type and have a different reason to want to end civilisation and bring about a massive reduction in the human population. These sort often (I hesitate to say always) dislike (sometimes, I dare say, dislike is not strong enough) humanity because of the environmental damage caused by the species homo sapiens sapiens.
The difference between the two sorts is at least two fold, one would doubtfully care about how to get to primitivism (so long as it didn't cause too much environmental damage, though there are many who predict massive environmental catastrophe), and the other, to stick to the anarchist principles must refuse to promote oppressive, hierarchical, non-voluntary methods (such as the forced sterilisation of nearly everyone...).
This leaves the anarcho-primitivists in a sticky situation then, how can they get to their preferred society? For some it may well be a case of, it is a critique and nothing more; for others, perhaps they are promoting voluntary population control (though it doesn't seem to be working in most parts of the world...).
So, thus there are two sorts (at least) of primitivist, the two intersect sometimes, often anarchists are environmentalists too, after all, but there are two distinct beasts.
For the environmentalists that also care about people, there appears to me to be only one sure solution. And that is industrialisation and sustainable development. History and demographies show us that in the richer over-developed world, populations are either stabilising, shrinking, or only slightly rising (discounting the effects of immigration). Where as, the major population growths have been in the under-developed world, and that is where they continue.
There are other critiques of primitivism, most of mine that aren't based around the question "how do we get there", center on the problem of prevent the re-occurrence of technology, the "other" (racism etc.) and hierarchy. To put it basically, without ICT (information communication technology), without the ability to communicate vast distances, and to store the reasons why technology is bad..., there is nothing to stop such things from coming back! Of course, there is the other critique, that both sorts of primitivism romanticise and ignore the (pre)historical facts. Firstly, humans are capable of causing massive amounts of environmental damage with the most rudimentary of tools (see the Sahara desert for example, as well as Australia and the Americas). Secondly, hunter-gather tribes weren't the anarchist utopias that many people like to imagine (see also my paper on communism). There was often fighting between different tribes, and there were strict hierarchies within tribes (the chief and witchdoctor on top...). Again, technology is required to preserve the information that would stop environmental damage, and to rout the superstitious.
It is my opinion that the anarcho-primitivist critique of society has some weight. Not a large amount (I suggest that they are targeting the wrong target, and that it is not technology per say that is the problem, but rather the society around it).
Post-addendum: I have read that anarchism is the contention that there can be a free mass technological society. That primitivism (of all sorts) is not and cannot be part of anarchism (claim made by Andrew Flood in (among other places, no doubt) Is primitivism realistic? An anarchist reply to John Zerzan and others. "That a free technological society is possible is - as I have argued - the central point of anarchism."
http://www.anarkismo.net/newswire.php?story_id=1890 (accessed 19/02/2008) Using the definition that I use for anarchism, this is not. however, correct. Flood is welcome to his definition, I will continue to use my though. For those of you not familiar with it, it basically states that if a person desires a non-hierarchical, free, oppression-less, volunteerenist society, then that person can be called an anarchist. Very broad I know.
Post-addendum2:
"I would suggest that primitivism is essentially a catastrophistic, fatalistic, and historically deterministic philosophy---they think that all thosepeople are going to die off whether we like it or not, becuase of the predicted crisis. At which point the primitivists who survive will be able to start rebuilding an anarchist society, or whatever. No revolutionary intervention is neccesary---the crisis will destroy existing society for us, and then we can rebuild it how we like." by Nil, 2 Dec 2005 in a comment made in response to the Flood article referenced above and found at www.anarkismo.net.
(Are then primitivists our comrades? Well, I would have to say that they aren't really. We may well be "fellow travellers" on this road to anarchy, but even the anarchist primitivists have major flaws in their thinking, strategies and plans. As such, I reject all primitivists from the inner-inner circle of my ideological comrades. But, because of the ideas and reasons, because of the emotional desire (and end to hierarchy, and, perhaps, environmentalism), I would not say that the anarchist primtivists are enemies.)
This paragraph is also reproduced in "What is anarchism, an attempt at building a framework".