Hola:
 
Tienes dos opciones y depende de tus necesidades y la cantidad de links que tengas. 
Lo más sencillo es lo siguiente: 
Código:
 #METE LOS LINKS QUE QUIERAS
my @links = qw~
http://google.com/
http://yahoo.com/
http://altavista.com/
http://alltheweb.com
~;
my $item = rand(scalar(@links));
print "Location: $links[$item]\n\n";
  
Ahora, si ves que no te mezcla demasiado los links, entonces puedes intentar lo siguiente: 
Código:
 #METE LOS LINKS QUE QUIERAS
my @links = qw~
http://google.com/
http://yahoo.com/
http://altavista.com/
http://alltheweb.com
~;
#MEZCLAMOS NUESTRO ARRAY
array_shuffle(\@links);
print "Location: $links[0]\n\n";
sub array_shuffle {
  my $deck = shift;
  my $i = @$deck;
    while ($i--) {
     my $j = int rand ($i+1);
     @$deck[$i,$j] = @$deck[$j,$i];
     }
}
  
SALUDOS