A quick Google search shows that this is a pretty well-covered topic, see e.g. Reservoir sampling. On CPAN I see Algorithm::Numerical::Sample, plus maybe Math::Prime::Util's randperm, which is essentially the same as Athanasius's example (although I suspect it might be a bit more efficient).

Update: Now with Benchmark:

use warnings;
use strict;
use Math::Prime::Util qw/randperm/;
use List::Util qw/shuffle/;
use Benchmark qw/cmpthese/;

my $N = 10;
my $K =  5;

cmpthese(-1, {
    mpu => sub {
        my @range = randperm($N, $K);
    },
    shuf => sub {
        my @range = (shuffle 0 .. $N-1)[0 .. $K - 1];
    },
});

__END__

          Rate shuf  mpu
shuf 2496610/s   -- -31%
mpu  3598054/s  44%   --
[download]