On change de gouverneur... on change de porte-clefs. Pour le nouveau gouverneur, un prisonnier n'est plus un homme, c'est un numéro.
How should I understand "de" in the sentences above? In the first one, why is it not "le" or "un"?
de here is a preposition. As in English, prepositions are used to introduce complements and depending on the proposition used, the meaning of the verb may change (in English this is pushed a step further with phrasal verbs where prepositions are used to modify the meaning of a verb without introducing a complement; in French this is not possible although there is the possibility to have an implicit complement).
Changer may be used in constructs with direct objects (not introduced by a preposition) and indirect objects introduced by de and à. All of on a changé de gouverneur, on a changé le gouverneur, on a changé un gouverneur are possible (with sometimes several possible but more or less probable meanings). To add to the complexity, on has several meanings and the more probable one is different depending on the sentence, so I'll first explain the sentence using nous as subject and then look at how that change when using on.
nous avons changé de gouverneur means something like our governor was replaced without any hint about who decided that replacement;
nous avons changé le gouverneur means something like we replaced the governor. Which governor we talk about should be clear with the context due to the use of le. There are other meanings of changer which could apply in specific contexts.
nous avons changé un gouverneur means something like we replaced a governor. The governor is explicitly unspecified due to the use of un (in a context for which a precise governor could be implied, it is probably not that one – in fact using un instead of le in such contexts would be arguably correct but for sure misleading)
Now on is very often used with the same meaning as nous, but it has other meanings in which the person it refers to is not specified (in English the most common way to render this meaning is using the passive voice instead the active one, but using one or sometimes they can also be used).
on a changé de gouverneur could mean something like our governor was replaced or someone's governor was replaced, but the first one seems more probable.
on a changé le gouverneur could mean something like we replaced the governor but also the governor was replaced or they replaced the governor and here the second and third translations seem more probable. And see how close those are from our governor was replaced.
on a changé un gouverneur could mean something loke we replaced a governor but also a governor was replaced or they replaced a governor, again the later two seem more probable.
"de" is a partitive determiner. In the first sentence "On change de gouverneur" you could translate by the preposition "of". "We are changing of governor" is a litterally translation.
The verb "changer de" implies that the object will affect the subject. The subject could be the origin of this change or not. This is why the correct form is using a partitive determiner and not a definite (le) or indefinite (un) determiner.