My book of expressions states that it is a compound verb made from the two vocal sounds we use to express hesitance or uncertainty. The "hem" is from the "ahem" sound, the slight clearing of the throat that shows we are about to speak. The "haw" was originally "hawk," which is clearing the throat with more force.
From 1580, in Gervase Babington's A Profitable Exposition of the Lord's Prayer:
Hem (Hum) and Haw. As an expression for hesitancy, to Hem and Haw isn't recorded until 1786. But it is found centuries earlier in similar expressions such as to hem and hawk, hem and ha, and hum and ha, which Shakespeare used. These are all sounds made in clearing the throat when we are about to speak. When a speaker constantly makes them without speaking he is usually hesitating out of uncertainty, which suggested the phrase. Said the first writer to record the idea in 1469: "He wold have gotyn it aweye by humys and by hays but I would not so be answered. " The modern version is to "Um & Ah".