I've gone with the recommended Mastering Algorithms with perl, and also got Higher Order Perl and Perl Best Practices.

All excellent reading matter, but in IMO (apart from the first) not really addressing your prime need:

The theory is the bit I am missing...

I would strongly recommend Introduction to Algorithms, by Cormen et al. (ISBN 0262531968.)

Prior to that, however, if you don't (like me) have a mathematical background, a must-read is Rod Haggarty's Discrete Mathematics for Computing (ISBN 0201730472).

Update: Corrected ISBN. Thanks, parv.