where on earth does one start?

The modules that you already are familiar with. Examine how they do what you have come to expect from them. Or pick a Perl Monk, see if they have a CPAN ID and have a look at that Monk's modules. Or visit some list of people's favourite modules.

IMO, CGI.pm is a good example of how not to do things. Do use strict, do separate, do not let any source file grow as large, do use sane (small) export tags, do not provide system wide configuration and do keep documentation simple and to the point (again: do separate: move tutorials to their own documents).

Juerd # { site => 'juerd.nl', plp_site => 'plp.juerd.nl', do_not_use => 'spamtrap' }