Remembering Passwords

Passwords can be stored using hashes that don't store the password, but a number that represents the password. The hash typically cannot be turned back into the password so there is very little chance that a security compromise will net anyone the original password. For example, a simple hash might assign A=1 B=2 C=3, etc... and then sum up all of the values for the corresponding letters in the password. If you've used that password before, the hash will always match, but there's no way to get the original password by knowing the hash.

Thus, it is certainly possible to know whether a password was used previously without actually knowing what the password was. Whether or not any particular web site uses this method, however... you can't be sure.

EDIT - note that the example above is exceedingly simple, only meant to convey the concept of a hash. This is NOT how you should compute a hash in the real world, not least of which because of the prevalence of passwords that would yield the same hash.

EDIT 2 - a better link might be http://en.wikipedia.org/wiki/Cryptographic_hash_function, which describes hashes in the context of cryptography. The previous link to hashes talks about them more in the context of grouping data, which they can also be used for.