You haven't stated what you want to do with the data once you have it. So I've written the following for both single item lookup and output in order, using the same set of data storage:

use strict;
use warnings;

my ($key, %hash, @order);

while (<DATA>) {
    $key = substr($_,1,length($_)-2);
    $hash{$key} = <DATA>.<DATA>.<DATA>;
    push @order, $key;
}

# To look up a specific record:
$key = 'Record 3';
print "$key =>\n$hash{$key}\n";

# To output the records in order:
print "$_ =>\n$hash{$_}\n" for @order;

__DATA__
>Record 1
AGTCTAGTCAT
CATCATAAGAT
CATCAATCACA
>Record 2
ATGAACAGCAG
ATGAAGAATGG
ATAG
>Record 3
AGTCTAGTCAT
CATCATAAGAT
CATCAATCACA
>Record 4
ATGAACAGCAG
ATGAAGAATGG
ATAG
[download]