Unit loyalty
- build units in lands with lots of morale/loyalty buildings and high loyalty.
- titles
- win a few battles (doesn't have to be with your king)
- disband (or send to their glorious deaths) low loyalty units
- marry your princesses to your unit leaders

Of these, the best is win a few battles, the easiest is disbanding units.

mfberg