Actually, the comments on how Google deals with old passwords (still recognising them to retrieve a locked-out account), got me thinking on the pro's and con's of this, and whether you could use it to avoid people re-using old passwords in a relatively secure way. Not that I actually think you would want that (personally I think that 99% of "enforced best practices" for password use just result in people writing down their password; this is true unless the person involved really really recognises the importance of the password (e.g. it allows operation of a nuclear power plant), in which case there is no need to enforce the best practices in a technological way).
First let's look at how Google may have implemented their system in a relatively secure way. From the comments above I understand that when one loses access to their email and forgets their current password, some sort of recover-workflow is started, where one provides "evidence" of their identity. Probably at some point a human will make a decision on whether to restore access to that account. At that point they need as much evidence as they can find that you are you! Knowledge of a previous password can provide a hint.
Now the problems of storing old password hashes are as @tim mentions in his elaborate reply -- even through I suspect Google secures their databases a lot better than most others, a data breach can always happen. If however instead of storing a full 128-bit/256-bit password hash (salted), they only store the first 16 bits (for old passwords), then it will be impossible for an attacker to extract a password from this*. At the same time, if someone provides 2 passwords that match 2 of the 4 16-bit hashes stored, this is a large hint that the person is not a completely random hacker**.
Say that your requirement is to not allow any password that has ever been used before on the system for that user (e.g. your boss read somewhere that its a good idea and won't allow anyone to change his mind). Again I fully agree with @tim's assessment that storing hashes for old passwords is a really bad idea. So what if we use the suggested Google solution, and store only a small hash for a password? Problem is that if we use 16 bits hashes, we have a reasonable change of disallowing a password that was not used before, but has the same 16-bit hash. The birthday attack shows that for 16 bits, after 36 passwords there is a 1% chance that at least one new password gets rejected --- this may or may not be acceptable. More bits means that this chance gets smaller, but the information exposed by a hacked database gets bigger.
* If your old passwords are "monkey1", "monkey2", "monkey3", a hacker may still be able to pick up this pattern. On the other hand, since Google doesn't require monthly passwords changes, I expect people that use simple patterns, not to care about changing their google password at all.
** Again I want to make clear that it's nothing more than a hint! The whole idea of old passwords is that they have been changed because they might have been compromised. So knowledge of an old password is not even that strong a hint; probably they'll want you to scan your ID card or something before restoring access. It does however add a first layer of protection against some 16 year old kid trying to hack into a teacher's account, or a computer script trying to hack many accounts at the same time. 16 bits will mean that only 1 in 64k random password attempts pass.