The answers I'm looking for are not only "what does the official material state/imply" but also "what's worked in your own campaign?"
Here goes:
1) The legitimacy of the charter, and the secrecy of its true purpose.
My impression from what I've read is that the Sword-Lords (especially the mayor of Restov) is organizing the expedition under the nose of King Surtova (and w/ the king's authority), with the surface excuse of "anti-banditry/monster intervention", while keeping all the "but these guys are intended to found new nations and back us up in the coming civil war" under wraps. How far are they going to keep this a secret? Do the adventurers signing up for the expedition know that it'll be their responsibility to found a new nation, or do they all think it's just a simple bandit-hunt until book 2? That's an important thing for my players to know as they're making their characters.
If the adventurers signing up for the expedition know, what's to stop them from blabbing in about it in a tavern beforehand and blowing the whole deal out of the water? I find it very suspicious if every adventurer in Brevoy had heard about this "sign on to go carve out your own kingdom from the untamed frontier in the south" and Surtova's agents had not caught wind of this.
A king that oblivious (and with that many enemies) would soon find himself on the pointy end of an assassin's blade, and isn't the Surtovas' whole shtick is that they're supposed to be crafty scheming bastards?
2) The sovereignty/autonomy/independence of the new nations.
In "Stolen Lands" (page 7) it makes mention that the Sword-Lords' plan is the "establishment of four new puppet kingdoms,
all beholden to Restov’s swordlords and the rest of
Rostland". However, the new charter in "Rivers Run Red" (page 6) states "...hereby granted the right to rule. The nature and laws of rule are theirs to define, and the wellbeing of this new nation is theirs to protect...future relations between kingdoms might be mutually beneficial."
So how autonomous/independent are these new nations supposed to be? It seems to me the overall tone throughout the AP is "Rostland's gearing up for a civil war vs Issia, and expects their new buddies to have it's back (literally and figuratively) in the upcoming fight" (essentially, an alliance). Meanwhile the new nations can govern themselves as they want, provided they don't take hostile action vs. Rostland (like trying to annex Rostland hexes).
But "puppet state" implies something entirely different in a geopolitical sense.
A puppet state is a metaphor of a state that is supposedly independent but is in fact dependent upon an outside power,[1] it is nominally sovereign but effectively controlled by a foreign or otherwise alien power, for reasons such as financial interests, in fact anything but the common good.[2]
A puppet state preserves the external paraphernalia of independence like a name, flag, anthem, constitution, law codes and motto but in reality is an organ of another state which created or sponsored the government.[3] Puppet states are not recognized as legitimate under international law.
Essentially, the PC's kingdom would be Rostland's b$+!#, having to do what Rostland wanted, when Rostland wanted (that doesn't sound as fun to play as "run your own nation"). But how would Rostland even have the expeditionary military might to even enforce it's will upon a foreign land? I thought the whole point of their secret plot with the expedition was that they didn't want to stretch themselves too thin by claiming the Stolen Lands themselves, and they needed allies for the upcoming civil war because they were militarily outmatched vs Issia?
3) Empty Hexes
So it's my understanding that it's implied (though not stated) that GMs should fill out empty hexes with something interesting. Site-based adventures, for example. Is this correct? I recall someone on some forum actually totaled up all the static XP from pre-ordained encounters and hexploration and stated that it was just enough to get the PCs to the next recommended level for the next book in the AP. So I dunno if populating the empty hexes w/ adventures will screw up XP gain, but empty hexes are no fun.
PCs: "We explore nearly 100 sq miles, what do we find?"
GM: "Nothing"
PCs: "Booh!"
Also, I know that previous efforts at organized, large-scale settlement/colonization of the Stolen Lands failed, but I would imagine there would be at least some little thorps/hamlets/villages/freeholds (and not ones that are all monstrous humanoids) eking out a living in a few of the more hospitable corners of the frontier. The excellent KM-supplement adventure Cold Mountain from legendary Games had a little tribal village nestled in the mountains.
I mean, it's supposed to be a "bandit-infested wilderness", but who do the bandits have to steal from? Each other? The whole thing that makes criminals, well, criminals is that they prey on innocent, honest, hard-working people. They're parasites, essentially. If they were self-sustaining, they wouldn't need to steal (incidentally, the bandits use the same stats as hunters in the Wandering Monster table in "Stolen Land". On that note, how much trade comes up through the Stolen Lands from Mivon and the rest of the River Kingdoms? I suppose the bandits could ambush travelers, but if it's that dangerous of a region, most travelers would be wary and well-armed.
1) It is heavily implied that the adventurers do not know they are intended to eventually found a kingdom, and based on the information in the AP you're right, it would blow away the entire secret plan of Restov if the PCs slipped up. Of course, you could also do some fun stuff with that, with spies finding out about the plans and tailing the PCs, assassins, etc. Good plot hook either way. In the Kingmaker campaign I started (it's our side campaign when we can't run RotRl due to missing players), we've only played one session so far but the PCs were basically brigands who were given the choice to take the writ and and work for the kingdom, or rot in a cell. They don't know they're set up to be puppets of Restov in the upcoming civil war, and the idea that these lawless brigands will eventually be thrust into ruling a kingdom makes it all the better.
2) I think the sovereignty of the new kingdom extends to the ultimate campaign kingdom rules, so the PCs are able to build up their new settlement with buildings per those rules and with support from Restov. I'd have to go back and reference the AP materials to give a better answer.
3) For empty hexes, I think it's largely up to you what you do with them. IIRC, the Greenbelt's non-bandit inhabitants are mostly hunters and trappers who occasionally venture to the outpost to sell their goods. There might be some hunter camps, but the outpost the PCs start at is really meant to be the last bastion of civilization before entering the wilds. You could put full adventures in there, or you could put smaller encounters in there, or you could roll for random encounters based on the random encounter tables in the AP, or anything else, really. If you have your own ideas for mini-dungeons those might fit well into a hex. Smaller modules might work too, such as Master of the Fallen Fortress (which is a free level one adventure! and can be easily adapted to take place in the Greenbelt instead of outside Absalom) and only takes a little time to run and complete.
The most appealing aspect of Kingmaker, in my opinion, is the fact that there is so much to explore in the wilderness, and it is left entirely up to the GM to determine what is there. The concept of an "open world" AP is great, so get creative with those empty hexes, because they provide more flexibility and creative freedom than almost any other AP.