I believe you can think about two views on government's origin, shallow and deep.
So you have shallow ex nihilo, which would mean "we rule, because we rule, we don't need to tell you why". But there are many states that claim their origin comes from things like "will of God" (medieval kings), "will of people" (modern democracies), etc. Many people don't consider them ex nihilo then, especially if they support the system. I find them as 'ex nihilo' as any other on deeper level. There are no things like "will of people", "will of nation", we don't know of any god who approved someone's reign.
The bottom line is that each government's "rights" to govern are made up, one way or another.