First, I had trouble with __END__, seemed to work better with __DATA__.

Here is the same thing looking a little more perlish and minus the deprecated FONT tag and BODY attributes and not using header tags to provide large text. Putting style back in using CSS is left as an exercise for the reader.

#!/usr/bin/perl -w
use strict;
use CGI qw(:standard);

my $quip    =    "";
{
   $/ = "%%\n";
   rand($.) < 1 && chomp( $quip = $_ ) while(<DATA>);
   $quip = $quip || 'Doomed! No Fortune Found.';
}
print header(),
      start_html( -title => 'Fortune Teller Says...' ),
      p( $quip ),
      end_html();
__DATA__
[download]