Some ground rules for creating characters:
This adventure starts at 1st level, with brand-new characters. Does it make sense for Lady Jamandi to be handing out settlement charters to random unknown schmucks off the street? No, not really. But she's doing it anyway.
You can use any official Paizo source (except other Adventure Paths). If I don't have something and it's not available on the
Archives of Nethys, I'll buy it, but I have most of the common books. (Please, just make everyone's lives easier and pick stuff that's in the Archives of Nethys.) You can access Uncommon options if you make a good case for it. I wouldn't bet on accessing any Rare options.
I strongly recommend choosing one of the backgrounds described in the
Kingmaker Player's Guide, mostly because these have useful plot hooks and Lore skills built in. You can take a background from elsewhere if you really don't like these (especially for INT-based characters, the choices are thin), and I'll try to tie it in at some point, but I can't guarantee it.
Social encounters and investigation sequences are pretty important in this Adventure Path. I wouldn't say they're more important than combat, but a character who can do nothing but chop up monsters will definitely be bored and possibly a liability at several points, including the very first scene. You will have a better time if your character is somewhat competent in at least one of the main social skills (Diplomacy, Deception, Intimidation).
However, make sure you're useful in combat as well. Seriously. The Stolen Lands are not a safe place.