Seems to come up quite a bit, so here's as much about leadership/authority as I have worked out so far.
For all skills you have two scores associated with your hero. One is for the field - eg, wood, metal, offence, sociability, etc - and the other is for the specific skill - woodcutting, leadership, etc. Each field has three skills (although not all are implemented yet). Your hero's total score at a certain skill is the average of your field and skill score. For leadership that makes it the average of your sociability and leadership.
It is this hero score that determines your authority/dominance. This makes authority the average of your sociability and leadership, and dominance the average of your fauna and taming.
Your overall ability at any skill is a weighted average of your hero's total score, your equipment, your companion's skill and your surroundings, plus any bonus from jewels or potions. The first four contribute as 40/30/20/10% of their totals.
You (or a companion) will have a chance of levelling up their skills when you are carrying out any task within 5 difficulty of that skill's score. So let's say I'm cutting oak trees which has a difficulty of 17. I can raise both my skill (woodcutting) and my field (wood) scores as high as 22, along with the woodcutting scores of any foresters who happen to be with me while I'm chopping away.
For leadership that means your leadership skills (sociability and leadership) can be raised to the difficulty of any given recruit plus five levels, provided you are willing to grind and spend the gold. Obviously you need to reach the overall ability to beat their difficulty in the first place, which generally means a good companion and tool (generally a tabard) plus a jewel to boost your ability.
A Page will have 10 +/-3 leadership base, plus any levels they gain. A hemp short tabard costs 7s 90c and gives 6 leadership, with better often on the marketplace (although be aware you need to be within 15 points with your hero to use such an item so can't leapfrog too far ahead that way).
The obvious grind targets are the Big Guy in Craneharbour (5 difficulty, 1s per attempt) and Scholar in Hawkoria visitor's district (9 difficulty, 3s per attempt). Note that there are plenty of worthwhile companions you could get some grind levels out of as well if you have a concession to stash them in while not using them. A Guard (Raven Inn, 8 difficulty, 10s per attempt) makes a nice addition to any combat team at lower levels. Expensive, but if you want one any way it's probably best to get one early while you will still level from it rather than wasting extra cash on Scholars you won't use.