Conquest and strength certainly played a role in the beginning, but unless there is some way to justify rule without violence then the state could never have lasted. History demonstrates that opinion of right (Hume) is far more effective and enduring than brute force.
For myself, I am sympathetic to the religious perspective (and I happen to be a theist) to explain the creation of the state, and while there might be exceptions, the ancient world is loaded with examples to support the claim. In ancient Mesopotamia, political power was held in the hands of the priests, who were responsible for the process of divination, or reading the will of the gods from nature. Because the people accepted their teachings and practices (which probably evolved from a successful shaman from earlier times), they developed political authority. The priests were, essentially, the directors of the economy, operating out of the temple. The people existed as labor for the gods, and the priests directed. Kingship later developed and was explained as a divine office. The same was true in Egypt.
The point here is that religion and politics were essentially fused into a single culture, creating theocracy. Irrespective of the good intentions of rulers and priests, religion formed the basis for political authority and legitimated rule in the ancient world. This is why anyone who attempted to expand political authority had to due so under the guise of religion - the Akkadian kings took a great leap towards centralization, having themselves declared to be divine. In Egypt, Akhenaton attempted to destroy the power of the priests by declaring their gods null and void and instituting monotheism with himself as the head. Later, conquering powers (Persia, Greeks, Romans) would pay deference to local gods for the purposes of political stability, an action that explicitly recognized the importance of religion to political rule.
The pattern that emerges is that whatever the religion of the masses, the state will align itself to it. Christianity was a thorn in the side of Rome for centuries, but grew too big to deal with, so as the Empire crumbled, the Roman state adopted Christianity. Germanic kings later became Christians and enjoyed obvious political benefits (Clovis). Eventually, states in the early Middle Ages aligned themselves with the Catholic Church, which served as a public education system, teaching people to obey the state so long as it supported Church policy.
In the modern era, with religion falling by the wayside, the state needs to be in control of public education directly to legitimize its rule.
Political authority rests on opinion of right, or acceptance of the double-standard as Clayton puts it, and religion is a potent opinion that ambitious men seek to align themselves with.