you could just loop over the search Criteria doing a new grep each time (the last line is there to skip out once the @newArray is empty) ie.,

use strict;
use warnings;

my @largeArray = (
     "this is a test",
     "this is another test",
     "that is another test",
     "test this is another",
    );

my @searchCriteria = ("another", "test");

my @newArray = @largeArray;

foreach my $criteria (@searchCriteria) {
  @newArray = grep { /$criteria/ } @newArray;
  die "Nothing Found\n" unless @newArray;
}

print join "\n",@newArray;
[download]

update: Since $criteria can be many different things including chars that might need to be escaped you might want to change /$criteria/ to /\Q$criteria\E/

update2: changed the ugly: last unless @newArray or die "Nothing Found\n"; to something nicer to look at. (die "Nothing Found\n" unless @newArray; )

-enlil