Try this wikipedia page:
[ame="http://en.wikipedia.org/wiki/History_of_Sumer"]History of Sumer - Wikipedia, the free encyclopedia[/ame]
As you can see, they believed that their civilisation arrived at its location fully formed which, to me, denotes they they may have believed in some divine agency. Many civilisations believed that their leaders (monarchs, whatever) were descendants of gods: the Anglo-Saxons traced their kings back to Woden; the Egyptians, of course, believed that their monarchs were
Which leads me to my next point. The main prerequisites of being a king are:
1. Being a murdering bastard, even if by proxy. Nice monarchs are rare and don't last.
2. Brains are a big help. But not strictly necessary: people with brains can be hired. Most thug kings of England had brainy cohorts, but the really successful ones had brains as well as a murderous, ruthless streak. Edward I, Henry VIII, Alfred the Great being just 3 examples.
3. It helps to claim descent from or close relationship to God or gods. This legitimises a monarch (God or gods are underwriting his kingship), and thus remove the necessity of constantly using violence to keep his crown on his head and his head on his shoulders. Also, threat of divine retribution for acts of defiance against a king was a very powerful lever. In short, religious leaders and monarchs collude to keep social order, and hence one legitimises the other. Frederick Barbarossa (Holy Roman Emperor) probably made best use of this.
Something resembling kings must have happened quite early on in Human history. However, I do not think that kings were initially just thugs: human populations were very, very small, and hence there was little competition during our hunter gatherer days. More important, most likely, was the ability to guide his tribe to new hunting grounds, find shelter, make the right decisions etc. Kings as we know them were probably a result of Neolithic period settling and farming: and as human population grew, (which took a long while), prime land would need defending.
Ug the Great was one of my ancestors....... we've not progressed much since