In Prisoner of Azkaban, Professor Dumbledore explains to Harry why he cannot convince the ministry that Sirius is innocent. Yet, in the beginning of Half-Blood Prince, the Minister of Magic admits to the Muggle Prime Minister that Sirius Black was innocent:
‘Is Serious Black with – er – He Who Must Not Be Named?’
‘Black? Black?’ said Fudge distractedly, turning his bowler rapidly in his fingers. ‘Sirius Black, you mean? Merlin's beard, no. Black's dead. Turns out we were – er – mistaken about Black. He was innocent after all. And he wasn't in league with He Who Must Not Be Named either. […]’
– The Half-Blood Prince Chapter 1: The Other Minister
What has changed that has made them admit his innocence?
Sirius's body disappears in the fight in Order of the Phoenix, so there's no evidence left that he has fought there. Pettigrew is still in hiding. There's still only Harry and Hermione's word against Snape's story that would prove Sirius's innocence.