"Multiple-line mode" just means that ^ and $ can match embedded newlines.
No other magic. If you don't have ^ or $ in your regex, multiline mode (or
lack thereof) just doesn't matter.

Perhaps "multiple-line mode" is a misnomer. How about "magic ^/$ mode"?
Without the magic, ^ and $ match the beginning and end of the STRING.
With the magic, they match the beginning and end of a text line.

Searching for /^From /

  multi-line mode:
        will find any line in $_ beginning with "From ";

  default mode:
        will be true onlyif $_ begins with "From "

So, if your whole spool is in a variable (such as $_), you can count
lines beginning with "From " with with:

 ___ perl 4 ___                          ____ perl 5 _____

 {
   local($*) = 1;                  
   $count = 0;                           $count = 0;
   $count++ while m/^From /g;            $count++ while m/^From /gm;
 }                                                                ^--- multi-
                                                                       line

(the perl4 way will work with perl5, of course, but is not the "approved" way)

It's important for your understanding to know what would happen if
  1) you forgot to set multiline mode.
  2) you used /\nFrom / instead of /^From /

Think about it a bit. Answers discussed below.

-----

If you don't already have the whole spool in a variable and don't need to
do it that way, Lawrence Kesteloot already posted something that should
help.

|>      $/ = ""; $* = 1;
|>      if (/\n\nFrom.*/)
|>      {
|>        $count++;
|>      }

Just to comment here, had you used 'while' rather than 'if', *AND* used the
/g modifier, you would have been close. All you would have need to do
then was insert a
        $_ = <>
before the if line (-:

(oh, and you would have missed the first "From " in the file if it was on
the first two lines.)

Your mail system may well be different, but many (most?) UNIX mailers
will ensure that only start-of-message lines will begin with 'From '.
Try
      echo 'From me' | mail <yourself>

and you'll probably see that the mailer inserts '>' or whatnot in front
of the "From" so that it doesn't look like the start of a header.

--------------

It's important for your understanding to know what would happen if
  1) you forgot to set multiline mode.
  2) you used /\nFrom / instead of /^From /

If you forgot to set multiline mode with
        m/^From /g,
the ^ would only match the beginning of the string. Thus, $count would
be either 0 or 1 depending upon if the very first line started with
"From " or not.

If you used
        m/\nFrom /g
then multiline mode wouldn't matter -- only matters with ^ and $.  The
result would be the same as m/^From / (*with* multiline mode) UNLESS the
very first line DID begin with "From ". Such a line would be matched by
m/^From / but NOT m/\nFrom / since there's no \n before the very first
"From ".

Go ye forth and practice unto perl.