Not quite sure how to phrase this – I’m looking for a book on the history as well as philosophically and judicial aspects of power, legitimacy, etc. Some question that I imagine could be addressed: How was the divine right of kings justified? When did the idea of a state as legal body originate? How was legitimacy related to symbols and regalia in the middle ages?
Edit: If possible, I'm looking for fairly recent and easily comprehensible books rather than original works of philosophers, etc.
My gut says Antonio Gramsci and his ideas on cultural hegemony, Peter Kropotkin's book Mutual Aid, Thomas Hobbes ideas on political thought, and Michel Foucault's writings on "power".
Edit:
History of the Theory of Sovereignty since Rousseau
http://socserv2.socsci.mcmaster.ca/econ/ugcm/3ll3/merriam/sovrou.pdf
Certainly seems like a question that ers towards political philosophy - If you don't want to deal with that material directly, I'd look at collections/text books from political philosophy courses. I cannot say for certain (my copy is in the loft) but John Cottingham's 'Western Philosophy' should have a section on political philosophy, and each extract is accompanied by some context (which should include some historical details). It is however a philosophy collection, not the work of a historian.
I'd second the recomendations of Kropotkin, Hobbes and Foucault (Gramsci is not someone I'm familiar with). Social contract theory is interesting, historically. John locke and Thomas Hobbes are worth looking at in that regard. There are more modern theorist, but if you're looking for strictly 'historical' sources, then Jeremy Bentham and John Stuart Mill are also worth looking at. Some work on 'feminising' nature, throughout history, might be of tangential use (Merchant, C., 1980, The Death of Nature: Women, Ecology and the Scientific Revolution) - I believe merchant talks about the state, and civilization. Probably not exactly what you're looking for, but there's a lot of discussion about how concepts change throughout history, and how that affects power structures. Tangental, but it might help.
I'm not sure what political philosophy was developed in the middle ages, the only philosophers from that time period that I've come across are generally heavily influenced by religious concerns. Political philosophy as a distinct subject seems to arise during and after the enlightenment.
A couple of useful Stanford encyclopedia of philosophy articles - http://plato.stanford.edu/entries/medieval-political/ http://plato.stanford.edu/entries/ancient-political/ http://plato.stanford.edu/search/searcher.py?query=political+philosophy
I would search that website for more articles on the subject, they're a very good source and fairly accessible.
David Armitage's book, [The Declaration of Independence] (http://books.google.com/books/about/The_Declaration_of_Independence.html?id=RHlYssMw6oUC) (2007), is certainly not a comprehensive overview, but I think it's probably a decent starting point for understanding how (some) ideas of sovereignty and legitimacy entered the public discourse. Armitage is especially interested in how the emphasis on international recognition became a key ingredient for asserting the legitimacy of a state.
You already have a lot of great answers, but you might want to take a look at the work of James C. Scott as a way to come at the issue of power and the state from a slightly different angle.
The Art of Not Being Governed in particular might be interesting because of the way he focuses on the relationship of the state in opposition to people living outside of the state as one of the state's defining characteristics.