The title lord or lady was a term typically used to address individuals holding certain positions, such as noblemen. The term was also used as an alternate term for the Christian "God" (DS9: "Far Beyond the Stars"), and as a general honorific used by the Androids of Mudd for those they serve. (TOS: "I, Mudd") In ancient England, a lord might be refered to as "his lordship". (VOY: "Cathexis")
According to the script, Kruge was described as "a Klingon War Lord", thus explaining why he was referred to by this title. The title may also imply that was of noble descent, such as a member of the Imperial Family or other prominent House. However, there is no clear indication of aristocracy amongst Klingons and the concept would appear incompatible with their spartan warrior culture.