The only things more beautiful than stateless societies are the works of Professor J. R. R. Tolkien.
It is no surprise then, that Tolkien himself was a proponent of anarchy. From a letter written to his son in 1943: "My political opinions lean more and more to Anarchy (philosophically understood, meaning abolition of control not whiskered men with bombs) – or to ‘unconstitutional’ Monarchy. I would arrest anybody who uses the word State (in any sense other than the inanimate realm of England and its inhabitants, a thing that has neither power, rights nor mind); and after a chance of recantation, execute them if they remained obstinate! If we could get back to personal names, it would do a lot of good. Government is an abstract noun meaning the art and process of governing and it should be an offence to write it with a capital G or so as to refer to people."
With his characteristic wit, Tolkien lays bare his view on the absurdity of any entity possessing a monopoly on the right to force. But it's not this quote that is so compelling and beautiful. Understanding Tolkien's literary work in the light of this quote improves not only one's appreciation of his aesthetic talent, but gives him a thoughtful insight into the structure of a stateless society.
Consider the Shire. There is no government of which to speak, and the Hobbits get by perfectly fine. They work and produce in harmony, and resolve their disputes privately, by the consensus of community, to which they voluntarily submit themselves. They show themselves capable of a complex division of labor and have developed a prosperous spontaneous order, which arose exclusively from tradition and the Hobbit's inherent love of fellowship.
Or Consider Rohan. The feudal state has king, certainly, but the king's role is essentially that of the CEO of an organization of private military contractors. There is no mention of the collection of taxes, yet somehow Edoras and the king of the golden hall are sustained rather comfortably. This indicates to us that, desiring defense from foreign threats like the wildlings and orcs, the Rohirrim voluntary support the nobility. There is national defense without coercion.
We then examine Gondor, which might be said to represent the neocons of Arda. While the intentions of Gondor's nobles and government are undoubtedly noble, we see that they eternally are gripped with power-lust (Boromir) and paranoia (Denethor). Indeed, the most honorable man in Gondor's government is of course Faramir, who would rather abstain from politics altogether, and who refuses power -- the Ring -- when it is offered him.
All of Eriador is protected by the watchful eyes of the Rangers, by Beorn, by the Eagles and the Elves of Rivendell, by the men of Laketown, the Dwarves of the Iron Hills, and countless other voluntary organizations and individuals who do not act coercively, but instead are benefited by those they protect.
The books also give us a fantastic example of private justice. The Scouring of the Shire, which was a seen most unfortunately omitted from the films, shows us Hobbits who go bad, and attempt to organize the shire under a government. When the heroes return, they manage to defeat the perpetrators of coercion. If someone attempted to, say, remove a gang leader in Chicago, they'd be faced with substantial legal problems -- problems which don't face Merry and Pippin and Frodo and Sam, who live under the Shire's private system of regulation and law.
Contrast all this to the principal evils of the series: Mordor, Isengard, and Orcs. All these perpetuate hierarchical structures of government and society. Sauron and Saruman are inherently coercive and abusive, and their orcish minions employ regular slave labor, consciously arranging a culture where might makes right. Indeed, the source of all the trouble in The Lord of the Rings stems from the Ring of Power -- power is the singular greatest evil faced by the world, in the mind of Tolkien. Tolkien also recognizes that power is harmful even when possessed in smaller quantities than that held by the dark lord. Smaug, for example, is a powerful dragon, and, as a consequent of his power, is a Dwarf-eating kleptomaniac.
If we want to get really nerdy, we can find examples from The Silmarillion. Herein, we find themes of libertarian free will -- as in the case of Turin's struggle against his fate -- and countless cities that we could label covenant communities, like Gondolin and Nargothrond. Again, the evil is coercion, whether in the form of Orcs and Balrogs and Morgoth, or the story of Eol the Dark Elf.
It is significant that for Tolkien there is no internal political strife, and that there are very few instances of political power being organized to coerce the subjects of a kingdom of province. In recent times, with the advent of the highly political Song of Ice and Fire, Tolkien has been critiqued for his lack of governmental acumen. This critique fundamentally misunderstands Tolkien. His lack of internal politicking is instead to be commended: he illustrates the structure of the stateless society in a beautifully rendered story that is as aesthetically fulfilling as it is politically insightful.