Maybe this is out of PIC discussion range, but I have used SIMTEK STK12C88 (
32*8 nvSRAM)  ( 28pins DIL).
It is like SRAM, but it has EEPROM mirror. RAM is moved to permanent ( =
nonvolatile) part by store and read commands under sowtware calls.
I have tried these in my 8051-project. Assebley source available.

Simtek has homeplace http://www.csn.net/simtek or
or http://simtek.com/simtek/docs/ProductList.html.

They also have hardware Autostore-products ie.after power down they
automatically store RAM to EEPROM. They need 100uF power capacitor and tree
resistors to detect power down. They promiced to deliver first 32k*8
autostore device for me for christmas. Let's see..
---------------
I have also tried 128kbits ( 16*8kBByte) XICOR X25F128P 8-pin FLASH device.
I works well, but it need 32 bytes ram to write one byte to device. Maybe
sombody knows better way.

Pekka
Pekka Ritamaki PROBYTE Oy Nirvankatu 31
FIN-33820 TAMPERE Finland http://www.sci.fi/~pri
Electronics product design: hardware+software+development tools
phone INT +358-3-2661885 fax INT +358-3-2661886