Government and the State
I think the government-state distinction is a useful construction, a way of looking at things. I see the state as the shell of the government. The idea of rule, of some ruling others, is the essence of government; the state is the social structure which grows out of the practices of government (basically, the engineering of the tools of coercion: war, terror, fraud, propaganda, secrecy, surveillance and so on) into a permanent, self-replicating social structure.
In my historical myth about the state, government begins as an agreement between property holders, especially slavemasters, to recognize and defend one another's property (an ongoing and laborious task, since others desiring property may attack property-holders and the property itself, if of humans or other animals, may revolt or run away) and to band together with them in attack other property-holders outside their association. In this stage of social development the government is simply an instrument of coercion which acts directly at the behest of and in the interests of its rulers. If there is a state is the same as the government.
As human communities became territorially permanent through the development of agriculture and industry, rulers would often find it advantageous to surround themselves with settled institutions and relations of social control, for example they might order their higher-ranking subjects into marriages and families, basing some preferment on legitimate descent. Other developments might seem advatageous: Multiple layers of property in land and buildings could be set up. Certain religious practices could be officially instituted and supported by the rulers, partly to placate the gods and partly to bemuse the lower orders. From these, offical arts and entertainments could be developed. Money might be invented and the rulers would see the profits in issuing it and controlling it. Trade in certain goods could be monopolized. Taxes, fees, tribute could be exacted. Along with these arrangements would go an ideology which declared that such things had always been and always would be. These are phenomena which we observe generally, in fact, nearly ubiquitously in the earliest states.
In general, the population could now be trained to subject themselves 'peacefully' and 'voluntarily' to the rulers; force, the explicit intervention of the government to coerce compliance, would be required only on special occasions (although it might be exercised for entertainment as well) and would often be attributed to its victims (as in the modern usage of the term 'class war' by some conservatives.) This social structure, outside the explicit government, along with the government, could be called 'the state' (in Latin status, 'standing', how things stand, the way they are.)
Complicating the picture is the fact that humans in or out of states live in dense social networks and have always done so since before they were humans, long before property and the state appeared. In order to enhance its grip on a community, the state organization conflates itself with many of these relations. For example, as noted above, states have constituted a state form of marriage and family, which would overlie and obscure the natural bonds between lovers and between parents and their children. These bonds could then be regulated and used to further attach people to the state structure: people begin to identify their attachments to and affections for their mates, children, parents and tribe with the state.
Eventually, the state advances to the point of making totalitarian claims on all of its constituents and the territory they inhabit. I think this brings us up to the situation in the historically known ancient world. Subsequently the state-government system, challenged by egalitarian, libertarian and democratic impulses among its subjects, begins to develop organs and functions which ape pre-governmental institutions of mutual aid, for example welfare programs. Moreover, non-governmental state institutions like guilds or corporations can be used as an alternative to overt government, thus masking the exercise of ruling- class power.