Do you know of any simple ways to make it respect the order in which they're specified when they're assigned at "my $regex ="?

Since your categories list is in alphabetical order, you could sort the keys in the print routine like:

for my $category (sort keys %data).

Glad to be of help!

Update: Just for the record, if the order of records was not in sort order, a few small changes would handle that situation.

At the top of the script, before the for loop, you would enter:

my @cat = qw/ Audio Graphics Network Settings System Utility /; # in y
+our desired order
my $regex = join "|", @cat;
my @files = glob "/usr/share/applications/*.desktop"; # as before
[download]

Then a small change to the print routine:

for my $category ( @cat ) {
    next unless exists $data{ $category };
    print "Submenu = \"$category\" {\n";
        . . . . .
[download]