How big are these lists? If they're not incredibly large, something like this should work:

# Assuming @list_a and @list_b

my %b;
$b{$_} = 1 foreach (@list_b);

my @list_c;
foreach (@list_a) {
    push @list_c, $_ unless $b{$_};
}
[download]

# Assuming @list_a and @list_b

my %b;
$b{$_} = 1 foreach (@list_b);

my @list_c = grep { not $b{$_} } @list_a;
[download]

Although not as nicely readable as Riales's solution, here's another option:

map{$setB{$_}++}@listB;
@listC = grep{!$setB{$_}}@listA;
[download]

Hope this helps!

Essentially the same question was asked today in removing a sublist. You might like to check the answers given there and perlfaq4 (arrays section) and Perl Cookbook, recipe 4.8 "Finding elements in one array but not another".

Re performance, the way to find out is to use the Benchmark module to compare the running times of various solutions.

A link to CPAN is often helpful: List::Compare.