You can read the rules here:
Basically each house had two leader tokens which matched two of their house cards. These tokens had to be in a land area with units of your house, and they added their strength to those units. When you inflicted casualties on units with a leader, the winner could choose to reduce the casualties by one in order to take the leader hostage.
Storm of Swords also included tactics cards. Each turn during your planning phase you would choose one of several tactics which would give you bonuses like extra strength when attacking, or extra strength when defending. The 'Secure Hostages' tactic allowed you to steal a hostage from any player who you defeated in battle that turn. If the stolen hostage was one of your own leaders, then you placed it in the area where you won the battle.
Three of the deck three Westeros cards (plus one of the options on the two deck three choice cards) allowed each player to execute one of their hostages. If you did, the house card that matched that character was removed from the game. (Note, that you could continue to use the house card of a leader who was a hostage, only executing him destroyed the card. This bothered people thematically, but it simplified things).
What really made leaders interesting though was that they each had either a Raid, March, or Consolidate power symbol on them. When you resolved an order of that type in their area, you could choose to discard it and then immediately resolve a march in that area. So forces with a leader could march during the Raid or Consolidate power phase. Leaders would either generate one power when they did this, or add one sword icon to any battles started this way. They could also have a different strength while marching this way.
There are several other details I skipped over, but that is the basic concept of leaders.