It will be defined in __PACKAGE__ - the current package.

update: The normal behaviour would be to define the method in the current object's namespace, but you are overriding this with  s/^.*:://.

update: see rir explanation below, then come back to this example.

An example:

package One;

sub AUTOLOAD {
    my $name = $AUTOLOAD;
    $name =~ s/^.*:://;
    *$name = sub { print "called $name inside ",__PACKAGE__,"\n" };
    goto &$name;
  }

package Two;
@ISA = qw(One);

package Main;

One->try1();
Two->try2();
$a = bless {}, Two;
$a->try3();
[download]

output:

called try1 inside One
called try2 inside One
called try3 inside One
called DESTROY inside One
[download]

update: more interesting example