The obvious approach is to create objects that hold both the value and the annotation, and to overload all interesting operations on these objects:

use 5.010; # just for say();
use strict;
use warnings;

{
    package Annotated;
    sub new {
        my $class = shift;
        bless \@_, $class;
    }
    sub value      { $_[0][0] };
    sub annotation { $_[0][1] };
    use overload '+' => sub {
        Annotated->new(
            $_[0]->value + $_[1]->value,
            "(" . $_[0]->annotation . ' + '. $_[1]->annotation. ')'
        );
    }
}

my $foo = Annotated->new(2, 'foo');
my $bar = Annotated->new(5, 'bar');
say +($foo + $bar)->value;
say +($foo + $bar)->annotation;
__END__
7
(foo + bar)
[download]

That might get hairy when you want to consider operations with non-annotated values, and it's a lot of work to overload all operators (though most of that can be automated

Apart from that I could only think of a custom perl runcore that traces annotations, but I wouldn't be the one to write such a core.