Works that way for me, I think better with a paper and pen.
I don't write out programs on paper, but I usually start by sketching out classes and methods on paper. The end result is faster than going directly to keyboard (for non-trivial problems).
I voted for Programming Perl, because it is complete.
My favorite Perl book is the first Advanced Perl, since I did Perl 4 before reading it (so others could read). I realized what I had been missing out of. I love it dearly.
(Update: Saw a few comments further down that Bart agrees with me.)
In reply to Re^3: If I could only own one Perl book, it would be: