I tried to make it as neat as possible.

Go for here-documents (perldoc perldata) to reduce the clutter of the single quotes and concatentations and double-quoted newlines:

use strict;
use warnings;
my %categories = ( A => [ 'B', 'Z' ], C => ['D', 'E'] );
my $category = param('category') || '';
my $subcategory = param('subcategory') || '';

use CGI qw/:standard/;;

# Generate javascript
print <<EOF;
<script language="javascript">
function catChange(newCat) {
    with(document.your_form.subcategory) {
        options.length=0;
        switch(newCat) {
EOF
foreach my $c (keys %categories) {
print <<EOF;
            case "$c":
EOF
    my $i = 0;
    foreach my $s (@{$categories{$c}}) {
        my $opts_params = ($s eq $subcategory && $c eq $category)
                ? ',true,true'
                : '';
        print <<EOF;
                options[$i]=new Option("$s" $opts_params );
EOF
        ++$i;
    }
    print <<EOF;
                break;
EOF
}
print <<EOF;
            case "Category":
                options[0]=new Option("Please choose a category");
                break;
        }
    }
}
</script>
EOF
# Well, now wasn't that fun?!

# Beginning of form
print start_form(-name=>'your_form');
print p(popup_menu(-name=>'category',
                   -values=>['Category',sort keys %categories],
                   -onChange=>
                       'catChange(this.options[this.selectedIndex].val
+ue);'),
        popup_menu(-name=>'subcategory',
                   -values=>['Please choose a category']));
[download]

Also, i did the following:

• locally scoped $c and $s since they're only used in the foreach loops
• added the 'use CGI qw/:standard/' line so that readers know it's required
• declared $category and $subcategory vars and initialized them to the param() call, but default to '' to avoid unitialized value warnings during the eq string comparison.

Another good way to tidy up the print statements besides here-documents is printf -- for example:

  printf 'options[%d]=new Option("%s" %s );\n', $i, $s, $opts_params;
[download]

And of course there is always Template Toolkit or HTML::Template and others, but that's probably overkill in this case.