Use Carp's croak and carp instead of die and warn, and then you can optionally turn on the stack traces as documented in Forcing a Stack Trace. Don't build your own stack traces.

As always TIMTOWTDI, but here's how I might do what you asked:

• If it's common for a method to "fail" and it can be represented by undef, that's probably what I'd do instead of forcing my callers to eval all the method calls.
• An error internal to the method that really shouldn't have gone wrong, e.g. assertions: die or confess (because I want to know exactly what happened where)
• Something that the caller of the method did wrong, such as pass a bad argument: croak, definitely
• If my method calls another method that might die or croak, it really depends on the situation, but often it makes sense to simply have that error be passed along.

This last point is something I've learned from my experience with exceptions: If the exceptions are designed properly, meaning they are true errors and not a normal mechanism to return values, then very rarely should any layer of my program be catching exceptions without re-throwing them except the very outermost layer. In a GUI, I'd like errors to be displayed to a user, in a daemon, they need to go into a log or email, and in command-line programs, they need to be displayed on the console. If a program has both (a) "exceptions" that mean something went very wrong and the program needs to terminate and (b) "exceptions" that mean a particular operation failed and the program may continue running, there needs to be a clear way for the program to distinguish these two types of exceptions. One way to do that is have (a) be fatal errors (e.g. die and friends) and (b) be special return values (e.g. undef). Sometimes you might be working with external libraries that take a different approach than yours, meaning they die more often, or they never die and return undef instead, that's one case where I might "transform" these exceptions using eval { ... ; 1} or return undef or defined(my $x = foo()) or die "foo() failed".