In this case, I would replace the cgi script with something a bit more complicated than the normal CGI::Application wrapper. Something like this that sets the start_mode:

#!/usr/bin/perl -w

use strict;
use CGI;
use My::App;

my $cgi = CGI->new();
my $mode;
if( $cgi->param( 'page' ) {
    $mode = $cgi->param( 'page' );
} elsif( $cgi->param( 'stats' ) ) {
    $mode = "stats";
} elsif( $cgi->param( 'new' ) ) {
    $mode = "new";
} else {
    $mode = "some_default";
}
   
my $app = My::App->new();

$app->start_mode( $mode );
$app->run();
[download]

Update: Uggg ... I like podmaster's solution much better since it appears the cgi-script is always the same. I've used the above approach - setting the start_mode in the cgi-script - when the the different modes of a multi-page cgi were different cgis (/cgi-bin/search, /cgi-bin/results, /cgi-bin/product, etc).