The empire was begun by Kahless the Unforgettable, who first united the Klingon people. Fifteen hundred years later, a clone of Kahless was installed as emperor, the first in three centuries, though given no political power. (TNG episode: Rightful Heir)
The origins of the Klingon Empire began in around 854 AD, the so-called "Heroic Age of Qo'noS", when Kahless the Unforgettable united the many warring tribes of Qo'noS. Under Kahless's leadership, the Klingons began to expand their empire across the planet and out into the galaxy following the development of warp drive in 922 AD (TNG episode: "Rightful Heir" and novel: Kahless; ST reference book: Star Trek: Star Charts).
However, the "First" Klingon Empire fell in around 972 AD after the Hur'q, a race from the Gamma Quadrant, invaded Qo'noS and pillaged many of the Empires treasures, including the Sword of Kahless. However, the will of the Klingons soon resulted in the Hur'q withdrawing from Qo'noS in around the 1300s. The Hur'q withdrawal left Qo'noS resource poor, and many departed the Klingon system to establish other colonies using 7 great starships constructed on the order of Ch'gran. (DS9 episode: "The Sword of Kahless"; and TLE novel: The Art of the Impossible).
Officially, the Klingon Empire is a feudal monarchy, with power residing in the Emperor, who is traditionally a descendant of Kahless. In reality, however, the power lies with the Klingon High Council, which is led by the Chancellor. The position of emperor was abandoned (but not officially abolished) in the mid-21st century, but was revived in 2369 when a group of clerics created a clone of Kahless, who was accepted as the new Emperor, albeit only as a figurehead. (TNG: "Rightful Heir")
The true power of the Empire is held by the Chancellor and the High Council, which consists of 24 members representing various Great Houses (essentially, the nobility).
Women are not normally permitted to hold seats on the High Council. (TNG: "Redemption, Part I") However, Azetbur, the daughter of Chancellor Gorkon, was permitted to succeed him as Chancellor in 2293. (Star Trek VI: The Undiscovered Country)
It is believed this was permitted because she was made the head of her house, due the unusual circumstances of her father's death. Various factions almost constantly challenge the leadership of the Empire, and so over time the Klingons have developed a strict and rigorous Rite of Succession to determine their leader. According to tradition, one may challenge the leader on the grounds of cowardice or dishonorable conduct and fight in single combat. Should the challenger slay the incumbent, he assumes the role as the new leader. (DS9: "Tacking into the Wind")
Because of the Klingon propensity for violence, some shrewd Klingon chancellors have redirected hostilities outward, when they would otherwise cause a civil war. In the 2150s, the Klingon chancellor instructed Duras to recapture Jonathan Archer after the latter escaped imprisonment on Rura Penthe. In this way, the chancellor focused the blame for certain internal problems on an external cause. (ENT: "The Expanse") Likewise, Gowron focused his soldiers' energies on invading first the Cardassian Union and later the Federation in order to avoid internal conflicts at home. (DS9: "The Way of the Warrior", "Apocalypse Rising")
Aside from challenges to the primary leadership of the Empire, there is also frequent feuding between the various Great Houses. Most often, the challenge is made on the floor of the High Council and resolved on the battlefield. However, on occasion, some "dishonorable" House leaders have chosen to make more insidious attacks by undermining the standing of their enemies; D'Ghor underhandedly attacked the House of Kozak in this way in the early 2370s. (DS9: "The House of Quark")