There's no canon answer that I'm aware of, but there is evidence in the books from the last part of Prisoner of Azkaban and running through Goblet of Fire that "when" is after the end of the Tri-Wizard Tournament and "why" is "because their agendas happened to coincide".
At the end of PoA, we see Minister Fudge dismiss the claims of Sirius's innocence as Harry & co being confunded. This has the effect of placing Harry on the wrong side of the Ministry, since later books make it clear that Fudge is paranoid about keeping his position and thinks of Harry as part of a plot by Dumbledore to usurp the Ministry.
Then, in Goblet of Fire, Rita Skeeter is shown as eager to muck-rake about anyone with any kind of power or celebrity. If there's no controversy, she seems to be happy to create one. When Harry's name comes out of the Goblet of Fire, there's an instant controversy, and even better, one that involves a notoriously publicity-shy celebrity.
Throughout the book, Skeeter continues to trash Harry's reputation, making him out to be a mentally unstable liar - and her readers love it (this is not explicitly stated, but if the Daily Prophet readership didn't accept and enjoy her character assassination, there would be threats to drop subscriptions and/or advertising, which would cause the editor to at minimum force her to tone down her articles).
At the end of Goblet of Fire, with Fudge refusing to believe that Voldemort could have returned, Harry realizes that Fudge believes Skeeter's muck-raking. ("You've been reading Rita Skeeter"). By this point, Skeeter has a significant percentage of British witches and wizards convinced that Harry is delusional at best, and the Daily Prophet is presumably still selling lots of copies, so the Ministry officially taking the same position is happy coincidence.
Of course, once the unholy alliance of Prophet and Ministry gets going, I suspect Senior Undersecretary Umbridge (the most likely culprit) would make sure to get some blackmail on the Prophet and prominent staff members, ensuring that the Prophet continued to speak in support of the Ministry.
None of this is explicitly canon, but it's implied by events in Goblet of Fire and Order of the Phoenix.