The general idea is that you want to identify where your program spends most of its time and focus your optimization efforts there. (E.g., subroutines that are frequently called or that take a long time to execute.) This is what Devel::DProf (and the dprofpp program) does for you.

Once you've identified those areas, you want to find out whether there are things in those sections that can be recoded to take less time. (E.g. something that is computed inside a loop the same way every time should be computed once before the loop starts).

The Wikipedia has an entry on Optimization that might get you started. You might also want to pick up a copy of Jon Bentley's Programming Pearls, which (while not Perl specific, despite the title) has a lot of good insights.