Just to add to Fletch's reply, check out Schwern's Refactoring article on perl.com.

I would add to Schwern's list after Pull Logical Chunks Out into Functions. Once that's done, I would look at the functions and determine whether or not they can re-factored into modules or libraries. I would favor modules over libraries most of the time. The only decision I would face is whether to OO or not - perlmodstyle.