The formation of nation states, to a large degree, occurred before the development of writing. Thus the information we have must be reconstructed primarily from archaeological evidence.
The beginnings of state formation lay in the neolithic period in which humanity first developed agriculture and created permanent settlements. Small bands of nomadic hunter-gatherers had no need for the complex mechanisms of political states, nor did they have the food surplus necessary to support a governing class.
One theory about the development of states argues that they began in response to the need for cooperation in complex irrigation projects in Mesopotamia and Egypt. Another reason the apparatus of the state was needed in agricultural societies had to do with land ownership. Investing time in cultivating plants rather than hunting and gathering is only worth doing if there is some guarantee that you will benefit from the harvest. Secondary to that is the need for organized forms of policing and self-defense to protect long term investment in livestock and crops.
Finally, the increased population size and density in agricultural communities, and the beginnings of urbanization, required complex social and political organization.