Just a few minor remarks...

First of all: don't use functions to create objects. Use a class method. It's much more consistent, and I'm sure, more easy to implement — why import constructors into your subclass?

So: change

# Loads user information, logs users in and out, controls cookies
my $user = My::Authentication::load();
[download]

to

# Loads user information, logs users in and out, controls cookies
my $user = My::Authentication->load;
[download]

More examples:

#allow user administration. (for registration etc)
My::Authentication::add_user($username, $password, { #hash to store da
+ta }, [ roles ]);
My::Authentication::del_user($username);
[download]

should be

#allow user administration. (for registration etc)
My::Authentication->add_user($username, $password, { #hash to store da
+ta }, [ roles ]);
My::Authentication->del_user($username);
[download]

Or you can split it up:

#allow user administration. (for registration etc)
my $suspect = My::Authentication->add_user($username, $password, { #ha
+sh to store data });
$suspect->add_roles(roles);
[download]

Second: I think you're having too many similar functions with related names. I prefer overloading. I think the default for require or must or whatever you call it (I prefer "require" over "must") should be to redirect to the login page, which you can optimally specify, if the user is not logged in and return a "forbidden" status if he is logged in but too low. Something like:

# Loads user information, logs users in and out, controls cookies
my $user = My::Authentication->load;

# require a user to be an admin or redirect them to the login page
$user->require('admin');

# require a user to be an admin or redirect them to a specific page
$user->require('admin', '/login.html');

# require a user to be an admin, or give them an "Access denied page"
$user->require('admin', undef);
[download]

I think there's much less to memorize.

Well, it could be nice if a user could "upgrade" to a more powerful user, when access is denied.

Oh, and for the sake of a good user experience: please remember what page the user tried to access when forced to log in. I hate it when on a webforum, the damn think forgets that I intended to comment on a post when it forces me to log in first. Please make it go back to where I wanted to go in the first place.

Well, this surely isn't the final API spec, it definitely needs some more hammering.