Anarchism and atheism are both defined in negative terms. As general paradigms they do not actually advocate any particular belief or system of organisation. They represent the lack of a belief. Atheism is a lack of belief in deities and religions, while anarchism is a lack of belief in governments and political groups. The literal meanings of the words are "without gods" and "without rulers". Both reject the alleged need for these things to exist and go even further in denying that they even exist as anything but concepts inside of people's heads.
While it may be objected that there is a difference between the two in that atheists deny the existence of gods, while anarchists do not deny the existence of governments, rational anarchists in fact do deny the existence of governments insofar as they are conceived of as anything but an aggregation of particular individual human beings. Anarchists are fully aware that the state is not an individual entity in itself so much as a particular organisation made up of certain people. It could be said that the anarchist is not interested in abolishing the state so much as abolishing people's belief in the state as a sovereign individual entity and the need for such an entity. For the state is fundamentally based on the ideological support of the populace, albeit in a passive and brainwashed manner. The state cannot be abolished in a meaningful or permanent way without a change in the ideas of people.
Both theism and statism share the belief in a need for a higher authority in order for the world to keep running and make people act morally. They contain a fundamental fear of what may happen in the absence of governments and gods. In the same way that statists believe that in the absence of government there would be absolute chaos, theists tend to believe that in the absence of deities, or at least their particular deity, morality ceases to exist and there is nothing to keep the clockwork of the universe running. In other words, both statism and theism share the belief that must society be planned in some way. In a religion, the planner is a deity, while in a political party or statist ideology, the planner is a state.
Religion and statism are also similar in that they bring forth the existence of multiple ideological groups that conflict with each other, with each group claiming a monopoly on morality and truth. Religious groups have historically battled each other to the death in the name of what they perceived to be virtue. Likewise, statism, especially as manifested in modern democracy, involves multiple political parties and political ideologies battling for the power of the state in order to force their preferences onto each other in the name of what they perceive to be virtue. The Hobbesian war of all against all is in fact a description of contemporary political democracy rather than anarchy.
In some ways, polytheism could be said to be somewhat less incompatible with anarchism than monotheism. Monotheism, the belief that there can only be one god, could be thought of as being similar to proclaiming there can only be one government, while polytheism, the belief that there can be or are multiple gods, could be thought of as being similar to proclaiming that there can be multiple governments. Therefore, polytheism could be considered more decentralised and tolerant in a sense, while monotheism is comparatively monopolistic. But of course polytheism still proclaims the alleged existence and need for deities, so the fundamental problem still stares us in the face.
It could easily be argued that organised religions came about directly as a result of attempts by states to control the gullible populations of times past. The Christian religion in particular could be viewed as a construct of the Roman state in order to more easily control the population by uniting them under one religion. The Jewish religion could likewise be seen as an attempt to unite the more decentralised tribes of ancient Judea into one political unit. In either case, the history of the state as an institution is clearly linked at the hip to religion. The most primitive and early rulers were literally thought of as being gods themselves or the descendants of gods. Furthermore, primitive deities in tribal societies were in fact family members who were ritualistically killed and eaten. This may give one reason to pause at the Christian notion of drinking Jesus's blood and eating his flesh symbolically for the communion ritual. Even when this notion and practise had worn threadbare, states used religious beliefs and institutions to bolster their power through the union of church and state. In some respects religious institutions used to be states in themselves.
Even in our comparatively secular modern age, political leaders are often treated almost as if they are gods capable of doing miraculous things. In the same way that religious people may pray to a deity in the hopes of their wishes coming true, political leaders are often looked at as people who can be relied on to do things that private citizens cannot do for themselves. In both cases, people are distracted from taking the responsibility necessary to pursue their desires themselves while expecting some higher authority to magically fulfil their desires for them. And when things happen to go their way, they always praise the higher authority for making it happen. Or when they actually do manage to do things for themselves, instead of taking pride for their accomplishments they act as if a higher authority is what made it happen.
To clarify, there are plenty of anarchists who are not atheists and plenty of atheists who are statists. I do not mean to imply that it is impossible for an anarchist to be an adherent of a religion. It would most certainly be self-contradictory for an anarchist to oppose voluntary and non-violent religious expression. But I do mean to imply that there is cognitive dissonance involved in simultaneously holding onto anarchism and theism in one's mind. For it does not make sense to reject the need for human rulers while maintaining that there is a need for a deity to function as a ruler. There is also cognitive dissonance involved in simultaneously holding onto statism and atheism in one's mind. For how can one deny the existence of and need for gods while still believing that there is a need for a state to function precisely as a god and while thinking of the state as a sovereign individual entity in itself?