Here's the long way -- I'm building a data structure:

#!/usr/bin/perl
use warnings;
use strict;

open (DATAIN, "EmpInfo")
  or die "Can\'t open file EmpInfo: $!";

#### try to parse file into a structure
my ($cur_emp, @cur_notes);
my %EmpInfo;

while (<DATAIN>) {
  my $line = $_; chomp $line;
  next if $line eq "";

  unless ($line =~ /^\-\ (.*)$/) {
    $EmpInfo{$cur_emp} = [ @cur_notes ] if $cur_emp;
    $cur_emp = $line; #move to next employee
    @cur_notes = (); #clear notes list with extreme prejudice
  } elsif ($cur_emp) {
    push @cur_notes, $1;
  } else {
    warn "note without a current employee? crap!";
  }
}
$EmpInfo{$cur_emp} = [ @cur_notes ]; #get that last one
close DATAIN;

#### add our comment
push @{ $EmpInfo{"John #4"} }, "He is too fat";

#### and send to stdout
foreach (sort keys %EmpInfo) {
  print "$_\n";
  foreach (@{ $EmpInfo{$_} }) {
    print "- $_\n";
  }
}
[download]

As you can see, the bulk of the code is in parsing your file. If you can, try to come up with a more functional data format. There are many simplistic configuration file formats on CPAN that would probably suit nicely. It'll make things much nicer in the future. In case you're confused about my data structure, %EmpInfo, see perldsc for some info.