I find the official definition of the state to be very useful. The state is the sovereign organization which holds a
To be a state, the organization (or collection of organizations and institutions) must be well-defined: even if part of that organization is secret, all individuals must know whether or not they are part of that organization. The organization might be in some sense beholden to or dependent on particular individuals or other organizations; what is important is that the legitimate use of violence must always "pass through" the organization that is the state.
The state must have sovereignty: there must be no higher legal authority than the organization to use violence. (States can and do go to war against each other, but that's not legal authority.) A state can delegate legal authority (usually by treaty), but as long as the state can in theory rescind that authority, it remains sovereign.
The state must be legitimate: the people against whom the state does or potentially could exercise its violence must recognize the organization as privileged to use violence. No organization — not even the Roman Empire — can rule by brute force; the population must at least passively acquiesce to the rule of the state.
The state must hold a monopoly: if more than one organization actually exercises violence, then those other organizations must have their privilege delegated by the one organization that is the state. In a federalist (e.g. Germany) or pseudo-federalist (e.g. the United States) system, the organizations that use violence (central and provincial governments) must cooperate closely enough to never fight amongst themselves; the collection of organizations forms a state. When Dwight Eisenhower sent federal troops to Little Rock to enforce desegregation, for example, governor Orval Faubus did not command the Arkansas National Guard to actually fight them.
The state must use violence: it can arrest, imprison, harm or kill individuals, without its members and agents facing social sanction (assuming their exercise of violence is validly exercised). It can also use the threat of violence to indirectly coerce individuals.
The state must exercise violence within a well-defined territory. This criterion separates the modern state from its feudal and imperial predecessors.
Given this definition, we can be very specific about alternatives to the modern state: relax or eliminate one or more elements of the definition, and you have an alternative to the state. Feudalism relaxes the monopoly and territoriality conditions; Pre-feudal imperialism lacks well-defined borders: the authority of the state is not uniform within its territory of influence, and regional governors, especially those far away could oppose the imperial government without fear of violent reprisal.
One interesting example of relaxing the territorial definition is in Neal Stephenson's book, Snow Crash, where the authority of franchises, the organizations that use force, extends to individuals, without geographic boundaries. The protagonist (cleverly named "Hiro Protagonist"), for example, is a "citizen" of Mr. Lee's Greater Hong Kong: Hiro can appeal to Mr. Lee for dispute resolution or physical protection from citizens of other franchises. Another interesting example is Eric Frank Russell's short story, "And Then There Were None," where no organization has a monopoly on violence: each individual is responsible for the exercise of violence; the only explicitly social sanction is noncooperation.
Since the state is at least capable of precise definition, I'm becoming even less impressed by anarchists who rail against the state, without being specific about what of the many conditions they would change. The official definition, like all good scientific definitions, is fragile. Because it is intentionally easy to break, that it's not actually broken shows its conformance to reality.
[Update 10/14] I was entirely remiss in mentioning that this definition of the state should be attributed to Max Weber in his work Politics as a Vocation.