I like it :-)

I agree with everything else, but I would suggest against...
o making it tied to CGI (or perhaps have My::Auth::CGI for that purpose).
o forcing the user (programmer) to use the modules own authentication system (perhaps make it optional, for convenience, though) - possibly authenticate a user with $user->authenticate(1), etc - this lets the user authenticate their users however they want (and takes some load off your hands ;-) )

That's all I can think of for now. I'm keen to see this finished :-)