What do we mean when we say history is a science?

I think you've summarized quite well that science is a verb - science is a method, not a thing. My answer is that history is practiced according to the scientific method.

To paraphrase Churchill, I don't have time for a good answer, so I'll write a bad answer and try to come back and revise in the hopes of making it better.

Kuhn made several claims concerning the progress of scientific knowledge: that scientific fields undergo periodic "paradigm shifts" rather than solely progressing in a linear and continuous way, and that these paradigm shifts open up new approaches to understanding what scientists would never have considered valid before; and that the notion of scientific truth, at any given moment, cannot be established solely by objective criteria but is defined by a consensus of a scientific community. Wikipedia:Kuhn

That describes history fairly well * History is full of paradigm shifts. Many of them are due to new technology providing new evidence. Some of them are due to simple re--examination of the prior paradigm - a recognition and re-examination of the assumptions made by prior generations. Sometimes it is due to theoretical changes - see Physiocrats. or Marixists vs everyone else.

• Scientific truth at any instant is based on communal consensus. I think the point you've made in your question is implied but not stated in Kuhn's statement - that the consensus is constantly tested by the scientific method. That the only way to change the consensus is to articulate a hypothesis and to collect evidence to prove that hypothesis, and the crucial feature of that consensus is the agreement to respect scientific methods and norms. There is not just an expectation that your proof will be challenged, but a requirement that the proof be challenged. But the challenge will be conducted by comparing evidence. (not through appeal to authority, or spectral concerns, or violence, or wealth, but through rigorous examination of evidence).

You asked about the predictive value of history, and I objected because I felt the question was phrased incorrectly. I agree that it is necessary that a hypothesis be predictive - but not of the future. Generally in history the hypothesis is tested against other data sets. (much like in sociology or political science). [Aside: I've tried to explain this before, but pretty much by definition history at this level is practiced at a level that is difficult to summarize in a few sentences. If it were that easy, it wouldn't worthy of that much respect. I'm going to try to discuss a single example, but I am summarizing debates that are more complicated]

Bailyn is known for meticulous research and for interpretations that sometimes challenge the conventional wisdom, especially those dealing with the causes and effects of the American Revolution. In his most influential work, The Ideological Origins of the American Revolution, Bailyn analyzed pre-Revolutionary political pamphlets to show that colonists believed the British intended to establish a tyrannical state that would abridge the historical British rights. He thus argued that the Revolutionary rhetoric of liberty and freedom was not simply propagandistic but rather central to their understanding of the situation. This evidence was used to displace Charles A. Beard's theory, then the dominant understanding of the American Revolution, that the American Revolution was primarily a matter of class warfare and that the rhetoric of liberty was meaningless. Wikipedia:Bailyn

This is a really good example. Beard analyzed the American Revolution in terms of the prevailing paradigm of the day - that it was driven by economic/class distinctions. Bailyn disagreed, and tested the hypothesis by going back to primary source evidence, analyzing a very large body of Revolutionary war era pamphlets to look for indications of class interest vs political interests. Bailyn's conclusions have carried the day. (as Kuhn would be quick to point out, the discussion won't end until the last Marxist dies. But that makes science more robust not less). Note the two themes - first the shift away from the Marxist/Whig paradigm to a more complex paradigm based on political thought and note the role of the new body of evidence.

Bailyn has been a major innovator in new research techniques, such as quantification, collective biography, and kinship analysis.7 [Ibid]6

Just reinforcing the need for scientific rigor and method in the practice of history.

Final thought to reinforce the predictive nature of history. I believe that Pauline Maier's work on the ratification of the American Constitution would not have been possible under Beard's older economic paradigm. Bailyn's hypothesis of the radicalism of the founders permits analysis of the types of radicalism.

I've failed to be terse here. There are other examples, but they are difficult to articulate quickly. (On the other hand, it is difficult to articulate any important scientific finding quickly and accurately; try to explain CRISPR or relativity or proton therapy or string theory).

Kudos to you for transforming this into a good question. Double kudos to you for making me put my money where my mouth is (??? Put my reputation where my snark is???) Well done!!

Incidentally, there was a good example in today's news about a coin presumed to be from Kilwa that was discovered in Australia. Kilwa, for context, was a late medieval nation of traders that were more or less based around modern day Tanzania.

Kilwa coins of that era have not been found beyond the Arab peninsula, except in Australia. So this discovery gives further credence to the theory of the Portuguese discovery of Australia.

As you can see, historians have put multiple hypothesis forward, and then as new evidence comes forward, they're eliminating theories that simply don't match the data. Which, to me as a scientist anyway, seems fairly consistent with what the scientific method is about.

It's arguably less testable than, say, astronomy, since new evidence requires digging in some more or less random place rather than deciding to point a telescope towards some area in the sky that has some known unusual or predictable feature. But personally speaking I'd suggest it makes sense to file history under science.

The problem, to me, is more related to spreading the knowledge about new historical findings to those who aren't usually interested in history, archeology, and so forth.

As to who one should blame for the discredit, there's a trope that's sometimes attributed to Churchill that raises that history is written by the victors.

That said, I suspect that 19th century historians -- e.g. Jules Michelet -- might deserve more of the blame than others, in that they developed plenty of narratives that were grounded in their nationalistic fantasies rather than sound evidence. The result of the latter is conspiracy theories running wild even today. For instance you can find traces of Aryanism in Russian antisemitic atlanticist occultists from the 19th century whose garbage theories continue to live with us today -- and that's just one ideology.