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.