To set up this answer, let me note that anarchism is a philosophy or ideology more than a political theory. By that, I mean that anarchism asks people to think in certain ways, not to act in certain ways. Political theories outline behavior by creating structures and institutions; one can live within a political system without really understanding its founder's intent, merely by conforming to the structures. Political philosophies or ideologies outline ideal principles under which people should organize themselves collecitively, but principles of that sort can only be applied through conscious, dedicated thought. This distinction may seem picky, but as I'll show in a moment it becomes important.
Now, one of the unavoidable (if often undiscussed) aspects of government is that government works through authority, and authority is power that is delegated from the populace to the governors. A leader is a leader because she says "Do X" and most of the people, most of the time, choose to go along with it. If no one went along with it, in what sense would she be a leader? There are obviously all sorts of ways to get people to comply — inducements and bribes, violence and threats, appeals to reason or intellect, appeals to norms or habituation, sheer charisma — and while these don't all have the same moral valence, they all have their own unique effectiveness. But the point is that a government simply cannot exist without a certain general consensus that it has a right to exist. Usually this is summed up under the term 'legitimacy': when we perceive the authority of a government to be legitimate, we accept its right to issue orders to the population as a whole.
A person whose authority is seem as legitimate governs, in the sense that people do as she says. A person who is not seen as having legitimate authority becomes another guy on a soapbox, shouting incoherently at the passing masses.
In an anarchist society, it is assumed that the vast majority of people have embraced anarchist ideology, which can be summed up by the principle that no stable, permanent delegation of authority is legitimate. Anarchists might agree to temporary governance for specific issues or concerns — delegating power to some person or group and agreeing to follow their orders because they have some special skills or aptitudes for a task — but they would not allow it to be established as a norm or an institution. Someone might gather an army and try to impose a government by force — assuming the he could find enough people willing to give up the principles of anarchism and follow him blindly — but none of the anarchists would see that as legitimate authority, and thus would not accept it as governance. They would see that 'leader' and her 'army' as a persistent nuisance or a group of immature and unenlightened thugs, and walk around them the way kids in grammar school walk around avoiding a bully. We sometimes see that situation in the real world after a revolution, where a deposed ruler still demands that he is the leader of the nation and issues commands from within his fortified compound, while the nation roundly ignores him.
If people don't give into threats, what would an ostensible government like this do? Kill everyone, and then put the soldiers to work tilling the fields and minding the shops? Governments need people to govern or they have no purpose, so a government can't kill everyone. But if people refuse to be governed...
Whether this is viable in terms of practical human psychology is a different question. It takes a lot of insight and strength of will to adhere to a philosophical principle strongly enough to risk death. But if we could find a nation of such people who refuse to be governed without conscious, free consent, it would be all but impossible to force a government on them.