States happen by contagion. One group organizes themselves with a flag. Then they become aware that there is another outbreak of humans "over the mountain," and that those humans may control different (maybe better) resources. So they seek to gain those resources and seek to bring the other humans into their group, under their flag. They implement this by 1) taking the humans and their resources by force, or 2) persuading those humans to bring themselves and their resources under the group's flag, or 3) agreeing to coexist voluntarily and to share resources.
In any event, the implementation involves calling the second group a name, maybe Transmontain, and the second group begins to call the first group a name, perhaps Uberberg. Each group is a nation, because each shares common birth circumstances among its respective members. Each group is a country because it exists in a territory. Each group may be a state because it has rules for interaction among its members and for relations with the other group.
As one group gains advantage over the other, it dictates its own rules and makes more demands about the rules of the other, often under threat of violence (ie, exercising its advantage by taking or withholding).
More and more as time proceeds the people of both groups lose their memory of what it was like before the two groups touched.