Here's an example of how one might implement it:

#!/usr/bin/perl -w

# Strict
use strict;
use warnings;

# User-defined
my $wordfile = "words.txt";

# Libraries
use FileHandle;
use File::Basename;
use Data::Dumper;

# Main program
my $iam = basename $0;


# Read words, saving file offsets
my $fh = new FileHandle;
open($fh, '<', $wordfile) or die "$iam:  can't read $wordfile ($!)\n";
my ($word, %word_offsets_by_letter);
while (1) {
    my $offset = tell($fh);
    defined($word = <$fh>) or last;
    chomp $word;
    if ($word =~ /^(.)/) {
        my $first_letter = lc $1;
        $word_offsets_by_letter{$first_letter} ||= [ ];
        push @{$word_offsets_by_letter{$first_letter}}, $offset;
    }
}


# Test (this will give 100 random words beginning with 'a')
foreach (1..100) {
    my $next = random_word_starting_with("a", $fh);
    print "Next word => $next\n";
}


# Subroutines

#
#  random_word_starting_with
#
#  In:  $1 ... the first letter of the word (eg. 'a', 'b', 'c', etc.)
#       $2 ... the open filehandle of the word file
#
sub random_word_starting_with {
    my ($first_letter, $fh) = @_;
    my $p = $word_offsets_by_letter{lc $first_letter};
    my $offset = $p->[int rand @$p];
    seek($fh, $offset, 0) or die "$iam:  failed to seek ($!)\n";
    my $word = <$fh>;
    chomp $word;
    return $word;
}
[download]

And if this is something you need to do a lot of, I like Zaxo's suggestion of using a database.