I'm Swedish from the start!
Since I'm Estonian and it's on the friggen map, ruled by Sweden, I, naturally want to be with the swedes. Current location: Dorpat.
Anyway, what I did was pretty much just follow the troops around, do a bunch of rep missions for them, fought wars with them, until someone of the nobles asked me if I wanted to be a merc, at which point the king dropped me about 700 gold a week. After I got some rep with the swedes, I asked the king if I could join and voilà, I was a swede.
Although I don't recommend them. The king's stoopid and just goes about conquering new stuff instead of defending his own. Also, when the king gets into a fight, other nobles won't assist him for some reason, so he's a liability in the group, even if he has ~250 troops. I almost wiped out the polish and after that the cossacks, but since the king didn't do the right thing, they have gained a lot of ground after that. Sad, really.