My solution isn't as elegant as the other algorithms already suggested, however, I think mine is more straight-forward, especially if you are still new to Perl:

#!/usr/bin/perl -w

use strict;

my @words = qw(fanfare apparate panacea parmesan albatross 
               albacore false vermeil candelabra beans);

my %hash;
foreach my $word (@words) {
    my $vowels = lc $word;
    $vowels =~ s/[^aeiou]//g;              # EXAMPLE B
    my @array = ($word);
    push @array, @{$hash{$vowels}} if defined $hash{$vowels};
    $hash{$vowels} = \@array;
}

my @sorted;
foreach my $vowels (sort keys %hash)  {
    push @sorted, @{$hash{$vowels}};       # EXAMPLE A
}

print " INPUT: @words\n";
print "SORTED: @sorted\n";
[download]

The above code provides identical output to what was suggested in the original question.

For the edge case where words have the same vowels in the same positions, there may be a desire to sort the words in alphabetical order. The above code would take the words "xaxexix babebib" (in that order) and print "xaxexix babebib". To make the code print "babebib xaxexix" instead, change the line marked "EXAMPLE A" to the following:

    push @sorted, sort @{$hash{$vowels}};
[download]

For the edge case where words have the same vowels in the same order but with differing positions, there may be a desire to have the a vowel that shows up sooner in a word to sort higher than a word that has the vowel show up later in a word. For example, the above code would take the words "babebib baebbib" (in that order) and print "babebib baebbib". To make the code print "baebbib babebib" instead, change the line marked "EXAMPLE B" to the following:

    $vowels =~ s/[^aeiou]/z/g;
[download]

We essentially replace all the non-vowels with "z", preserving the position of the vowels.

This was a great question. It is great to see the different ways a problem can be solved in Perl!