Several other ideas -

In addition to the 16F84 and 16F87x family, Microchip makes 12CExx parts
with 16 bytes of EEPROM internal. They're great if you can use 8-pin
parts.  I don't know if they're available yet, but I think there were
some bigger parts planned.

Dallas Semiconductor (www.dalsemi.com) makes 3-pin serial EEPROM devices
that interface through only 1 bi-directional pin.  They're a little more
expensive and more software work, but great if you are limited on pin
count or have to put several peripherals on a single bus.  You can put
any number of devices on the 1-wire bus.  They make A/D's, temperature
sensors, real-time clocks, memory, analog switches, etc.

External FLASH memory is usually parallel, not serial, although there
were some serial parts available several years ago.  Flash is the
economical choice when you need large memories.  We use a 512 K-byte part
that's around US$4.00, and it's a small one.  Larger ones are less
expensive per bit.

The least expensive external part you can use to get a few bytes is
probably the 24C00 or one of its siblings (24LC00, 24LV00, etc).  Use the
one that has the right voltage/power/write-cycle specs for your
application.  Some of these parts are less than $0.25 in quantity, less
then $0.40 in single pieces.

Someone mentioned that these parts go up to 64K or higher.  I know of
256K parts available from M'Chip, but  AFAIK, all serial memories and
most parallel memories are now advertised in bits, not bytes, so that
256K part is 256K bits, or 32K bytes, and that's the largest yet
available.  If anyone knows otherwise, please let me know, because we use
a lot of serial EE, and we stack them in groups of 4 or 8 to get larger
memories!

Don