According to Max Weber the state is "a human community that (successfully) claims the monopoly of the legitimate use of physical force within a given territory." Let's break this down bit by bit.

a human community . . .

Humans, as social animals, come together to form a multitude of associations that often have a communal aspect. This is natural for us. In today's world our associations may or may not be exclusive. We are members of churches, we are member of neighborhood associations, we are members of unions, etc. etc. Let us put our anthrocentrism aside and realize that we are not unlike other social animals in our desire to form associations. We just have a degree of complexity that appears unrivaled, to our knowledge. The state is an association and it goes without saying that an association of one doesn't make much sense. We need to find out what makes this association different and perhaps unique.

that (successfully) claims the monopoly of the legitimate use of physical force . . .

Here we encounter the trait of coercion that is fundamental to the idea of the state. The state, reduced to its smallest role, could be seen as a 'night-watchman state.' This is the state of the minarchist and some libertarians. With the monopoly on the use of force, the state is empowered to take on actions that the citizens in the state are unable to do themselves. In all other matters the citizens are free to do as they please. But the expanded states (Nanny State, Welfare State, Warfare State, etc.) all stem from this principle that they have the 'legitimacy' to do as they wish. Even the minarchist state allows for some level of coercion.

Any gang of armed thugs may be able to successfully claim this monopoly for themselves. But do minarchists have any idea as to what would give a morally sound justification for the state to have this monopoly? It seems that there is a healthy Hobbesian fear of a world without laws; minarchists seem to hold the idea that a state is absolutely necessary for civilization. Yet they are also fearful of a state that is out of control. Necessary, yes, but a necessary evil. And so we see a lot of talk about government governing with the consent of the govern, and all that.

What does one do with a state that is a necessary evil? How does one keep it from expanding in power and control beyond that which is deemed necessary? Who are we to trust? The people? The courts? Checks and balances? I don't believe that the minarchists have ever provided a sufficient answer of how to solve this problem.

within a given territory.

Despite being last in the definition, I think this is the key concept in how the state is defined. A state would be best defined as "a territorial monopolist of jurisdiction and taxation" in the words of Hans-Hermann Hoppe. The key here is that the state is a territorial monopolist and as a territorial monopolist the state is unavoidable. A simple anarchist call for the abolition of the state tends to focus on opposition to the coercion fundamental to the idea of the state. But states will exist as long as some individuals have the ability to exclude others from a territory and set the terms on which they may enter into the territory. By identifying the state as an unavoidable evil, not a necessary evil, I don't think that there is a burden of proof that requires us to 'justify' the state, unlike the minarchists.

It has been observed by cultural anthropologists that humans tend to have a tendency to view non-moving objects as property while moving objects are often left open to a free for all. It is far easier to enforce one's claim to a territory of land than to enforce one's claim to a group of deer, or wooly mammoths depending on your time period. Looking at human history, it seems very likely to me that we have always lived in groups within some territorial range. Settling down would only have given greater permanence to our lifestyle.

Imagine a society in which there was no state. Even in this society there would be some relationship between humans, either individually or in groups, and the land. Groups would form that would exclude certain individuals from territorial ranges. Even one person with a single plot of land could be viewed as a state. They may lack domestic politics, but in their interactions with the rest of the world their claim to being the sole monopolist of force for that territory may entitle them to state status.

The state as a territorial monopolist is often displayed with the 'Love it or leave it' attitude that many red state conservatives have. In a world in which all land is claimed by a state it is hard to imagine how one could exactly 'leave it.' While each state may have their own mechanisms for enforcing control, states as a whole have the powerful enforcement mechanism of having claimed all (or almost all) of the available land. If Henry Ford were alive today he might observe that we are free to live anywhere we want, as long as it is in a state.

If everyone had their own plot of land they would be given the choice to be free from coercion. As long as there are more people than plots there will be coercion. The state becomes an unavoidable evil and our goal becomes reducing the evil as much as possible and making life bearable. We may also have a secondary goal of trying to find ways to improve the ratio between people and plots. But I think we must grapple with how best to deal with the state.