In order to unlock a new East Empire Outpost in a Hold, the player must first gain the approval of the local Jarl.
Different Jarls can be convinced in different ways; below is an explanation of potential options that can appear, depending on the Jarl (to see which options are available for a specific Jarl, check out the Blessings misc quest pages).
The player can pass a speech check of varying difficulty. Certain Holds will require higher checks, and in some Holds, Persuasion will not be possible.
Persuasion can succeed or fail.
If the player has become a Thane of a Hold, this will replace the usual Persuasion option and the difficulty of the check will be reduced by one level. E.g. What would have been a Very Hard: 100 Persuasion check becomes Hard: 75 instead. The Thane option is available at every Hold (except for Raven Rock).
A Thane check can succeed or fail.
For certain Jarls, the player may discover a note, letter or document that can be used to blackmail or otherwise compel them into being more cooperative. These notes are sometimes found out in the open, kept in private areas, or locked away. This acts similar to the Thane option, reducing what would have been the usual Persuasion check by one level; it does not, however, replace the default Persuasion (if it is available).
The player must have possession of the note/letter/document for the option to appear.
Coercion can succeed or fail.
Considered the default fallback, the player may always simply pay a Jarl a certain amount of gold to gain approval. The amount of gold required varies depending on the Hold and the player's level of the Haggling ability. Higher levels of Haggle reduce the amount of gold required.
If the player has enough gold, this option will always succeed. If the player does not have enough gold, the Jarl will inform them and they may try again later.
If the player has unlocked a certain level of Illusion, they gain the option to use magic to cloud the Jarl’s mind, tricking them into accepting.
Illusion can succeed or fail.
Sometimes, certain Jarls will accept a Gift in exchange for their allowance of the East Empire. Usually a note can be found near to the Jarl indicating what Gift they would like and where it may be found.
Presenting a Gift will always succeed.
Certain Jarls will have notes indicating important information (Gossip) or notes indicating a task that requires doing (Favor). Bringing the Gossip note to a Jarl will give a new “Gossip” speech option. Completing the task on the Favor note will unlock a new speech option.
Gossip and Favors (once completed) will always succeed.
There are 3 perks that will unlock a special speech option with certain Jarls. These are mostly hidden bonus options, although the player will be given some hints of which Perks can be used via notes from Korrin.
Perks will always succeed.
To help the player discover more options, the player can find notes from Korrin by activating any East Empire Ledger after visiting a new Hold for the first time. (For example, if the player reaches Solitude, they could return to the East Empire Outpost in Whiterun and activate the ledger there to receive a note).
These notes will give the player hints about where to look for notes or items that could help the player convince or coerce the Jarl into granting their blessing.
All the Holds in Skyrim* have a clue available to allow the player to convince the Jarl without having to pass a speech check or spend gold.
*No clue for Winterhold is needed, as Korrin hands the player the book needed for the Gift option.