So how do we address the fact that historical materialism is unfalsifiable, and therefore inherently unscientific?

You may not be able to experiment on history, but you can experiment on how humans act under specific circumstances. Shouldn't any idea of history be at its core a study of social psychology?

It would be more correct to say that you could disprove historical materialism by finding sufficient examples of societies following a contrary economic pattern, say a society transitioning from capitalism to feudalism or from feudalism to huter/gatherer egalitarianism without some catastropic disaster wiping out most of the population.

Well I suppose that would disprove the deterministic aspects of Marx's ideas, but I was thinking more of how economic factors shape social/political structures and the actions of historical actors.

Falsificationism is unfalsifiable.

The mode of production, along with other material realities, determines social and political structures. To disprove that aspect of historical materialism, it would suffice to find societies featuring superstructures that are not ideally suited to the economic reality of a society, say a capitalist absolute monarchy (you may even make a case for Saudi Arabia) or an egalitarian feudal society.

Predictions of massive complex systems (society) are defacto untestable
Should all political ideology be abandoned and rationalia established