There's been quite a bit of talk here about good patterns to follow (Model-Vew-Controller) and good frameworks to use (
OpenInteract,
CGI::Application,
Apache::PageKit,
AxKit). If you really need it to work with CGI, you're more limited in what you can use.
As for code legibility, perltidy gives a good example, and both perlstyle and Tom C's style guide have good advice.
How much OO? It's impossible to give a very useful general answer. Enough to give good abstraction, but not so much that you spend a lot of time thinking about the OO constructs rather than the problem you're trying to solve.