I think choroba is proposing a solution along these lines:

#! perl
use strict;
use warnings;

my $target = 'kitten';
my $count  =  0;

{
    local $/  = "\n>";
    my $first = 1;

    while (my $string = <DATA>)
    {
        if ($first)
        {
            next unless $string =~ /^>/;
        }

        (my $header, $string) = split /\n/, $string, 2;

        printf "Header: '%s%s'\n", ($first ? '' : '>'), $header;

        $string =~ s/\n//g;
        print "string is '$string'\n";
        $count += () = $string =~ /\Q$target/g;
    }
    continue
    {
        $first = 0;
    }
}

print "The target string '$target' occurs $count times in the file\n";

__DATA__
not a header
kittens
>Header1
sushikitten
ilovethekit
tensushithe
kittenisthe
>Header2
sushikittAn
ilovethekit
tensushithe
kittBnisthe
[download]

Output:

19:57 >perl 1474a_SoPW.pl
Header: '>Header1'
string is 'sushikittenilovethekittensushithekittenisthe>'
Header: '>Header2'
string is 'sushikittAnilovethekittensushithekittBnisthe'
The target string 'kitten' occurs 4 times in the file

19:57 >
[download]

Hope that helps,