Well, the rebellion was founded by people who knew the truth about Palpatine and were never really swayed by imperial propaganda. As for the general populace, I imagine discontent among the populace began growing exponentially after the dissolution of the senate. The destruction of the Death Star would likely have spurred a lack of confidence in the Empire as well. Also, with local moffs and governors taking direct control of their respective regions without significant imperial oversight, in something resembling a feudal system, it seems highly likely that, given the tendency of imperial officials for violent suppression of dissent, many local populations would have been repressed and unhappy. Therefore, it is reasonable to suggest that many imperial citizens would have begun to romanticize the past Republic era, and the paragons of the Republic: the Jedi.
This would likely have been one of the driving factors behind mounting momentum in the Rebel Alliance between A New Hope and Return of the Jedi, despite setbacks like the abandonment of Yavin 4 and discovery and destruction of Echo Base.
