Well, since cryptography, like the hokie pokie, is what it's all about, I guess you'd use some form of cryptography. Evidently there's a module called Crypt for Perl, which contains some good built in ciphers. Below are two links detailing their use, among other things:
http://www.perl.com/pub/a/2001/07/10/crypto.html
http://www.perl.com/pub/a/2001/09/26/crypto1.html
(There's also some other Perl library that acts as an interface to openssl, which would also be worth examining)
The first is about symmetric cryptography, the second about asymmetric. Read the articles for the difference between the two. I think you'd want to go asymmetric, since you'd have no secure channel to transmit a symmetric key. Assuming this, I think you would then generate a key for the user when they create their account, and generate one their acount on your side which would be somehow in their file. And I guess you would then encrypt their password information for storage, then send them the encrypted data directly, and let them and their key do their thing.
Granted, it's a bit vague, and with a high probability of partial to complete incorrectness, but it's an idea. Also, get Apache.