Well, to get started I frame the scene for the player, along with some context surrounding their history. For instance, I might say: "Thelor, it has been six years since you joined the host of Nurunkhizdin. Through hard work and heavy drinking, you have advanced to the rank of Attack-lord and now command a division of 343 axes. Lately, Orc attacks have diminished significantly and some of your men belive that the tide has turned. One evening, Weapon-lord Gror sends for you and when you arrive, he looks as though somebody sprinkled sour-moss in his ale..."
And we go from there! Like I said, it really is almost a mini-mini-adventure. I make an effort to not make the twists so crazy that it would radically change how the character would've been played over the past games. That would be breaking the rules, I think. Everything else is up for grabs, though.
For instance, for the first five games both Thelor and I assumed through our conversations that Thelor's mother had died. One of his oaths was to her, and we thought he made it on her deathbed. Then, the flashback came -- and he saved her! Now, the player could've chosen to not have and kept with his original vision of the character. This, however, he thinks is better.