The first step would be to reduce the number of separate passwords that have to be used. That means minimizing/eliminating the use of outside vendors that interact with your users via the web. If there's some vital human resource service that is needed (testing, training, employee reviews, whatever), bring it in house rather than contracting it out to an outside vendor. Because every single outside vendor you use means another set of credentials to be maintained.
The second step would be to eliminate password expiration. This may mean eliminating people in your organizatoin who think that password expiration is necessary. Depending on that person's position within the company, that might be as simple as telling them to knock it off, or might involve a complicated scheme to convince another company to recruit them away. When all else fails, compromising photographs are always effective.
But as the situation stands, I have to maintain half a dozen passwords, many of which I only use once or twice a year. So they are written on a post it note in my desk drawer. Sure, that pisses off the data security people. But before they steal that they'll nip the $200 backup drive sitting on my desk.