I have fairly recently been through this process myself and I can assure you that it is a) worth it and b) not nearly as complicated as it may seem in the beginning. I think the trick is to avoid reading the computing science literature about OO design and just get your hands dirty ASAP.

I think the best way to start is to identify the need and the benfit, which gives you the right incentive.
For example, you might notice that your data-structures are gettng more and more complex and that your scripts are modifying values deep inside nested hashes of arrays or something like that (happened to me). Then you might think "wouldn't it be nice if I could just tell my script that this datastructure is an object that knows how to do certain things?", i.e. think of the interface you would like to use in an ideal world and then write an OO module to provide that. The satisfaction you will gain next time when you can write in another script My::ProblemSolver->solve_problem is worth the effort ;-)

Good luck!!