I always recommend learning by doing. A lot of CPAN modules expose an OO interface, allowing you to instantiate and inherit from them. Using those modules is an excellent way to ease into Perl OOP concepts. After you're there, learning how to create a class, and other OOP concepts used in Perl is much easier.
Trying to rebuild Perl application to Object Oriented style
However, this brings up the question, whether you are trying to rebuild an application in OO simply to make it OO, or is there a real need there. If something is already built in a procedural way, and works fine, rebuilding it just to make it OO can cause more harm than profit. Perl have ways to interface with such an application that allows creating OO-based components and you might learn better from interfacing with it whether it should be re-written at all.