The definition most used by Marxists is that of the non-Marxist Max Weber, which he partly derived from Leon Trotsky: "a state is a human community [a bunch of people] that (successfully) claims the monopoly of the legitimate use of physical force within a given territory. Note that "territory" is one of the characteristics of the state." (http://www.mdx.ac.uk/www/study/xweb.htm) The big question concerns the meaning of the word "legitimate." Is it a value judgement? or does it refer to a generally-based popular support for the state? (a materialist would say the latter.) In this view, the state is the Hobbesian Leviathan, which prevents the bloody war of each against all and allows "normal" life by monopolizing the use of force (and setting the limits on the "private" use of force).
In the context of Marxian theory, the state is necessary in order to enforce and preserve class rule (domination, exploitation, alienation). In a world dominated by a large number of states, in addition each of them is justified to the dominated by the defense of the country against others.
In the modern interpretation of the "withering away of the state," the state is seen as a _social relationship_ between the ruled and the rulers. It withers as the social relationship is revolutionized, i.e., as the rulers are subordinated to the ruled (in a democratic way, with democracy being more profound than that seen in places such as the US) so that the distinction between the state and civil society (that part of society that is not the state) is abolished. This is only possible if the class relationship is also abolished.
Abolishing exploitation isn't sufficient for a single country, however, since some sort of state is needed for national defense. Having popular militias is a good start, but modern military technology (nukes, etc.) suggest that militias aren't enough. World revolution is necessary to this story. Each of the revolutions would have to be a popular one, since socialism cannot be imposed with bayonets (i.e., from above, with force).
In the Marxian view, the process of the abolition of the state might take centuries. -- Jim Devine