Depends on how much data you want to store off chip.

Standard serial eeprom (i.e. 24LC256 type) - easily done, 32K (or more depending on chips used) off PIC storage, PBP supports it directly (thru I2CRead/I2CWrite commands), and so on...(and you could program the chip directly using the PICKIT2)

ATMEL Dataflash chip - not as easy as a 24LC256 type, only uses a few pins, can use PBP's ShiftIn/ShiftOut instructions to access the memory. But you have to learn how to access it first (not sure if the PICKIT2 can program those directly, I don't think so, but I could be wrong)

SD card - not so easily done, a few more pins than a 24LC256, have to write your own software/shifting code to access the card, but you can store a load of data on it obviously. Could load the files onto the card and then plug it in but you still have to write the software to access the FAT16/FAT32 data on it.

Hard drive/Compact Flash card - again, not so easily done, cheap, but uses a lot more pins than either of the above methods. And again, have to write your own routines to access the drive in IDE mode.

Probably a few more methods I've forgotten....

EDIT: and there is...
You could get a large PIC such as a PIC18F8722 and use it in the 'Microprocessor' mode where all of your program and data is stored off the PIC and accessed thru an Address and a Data bus (like the old school Z-80/6809E/6502/etc but with more memory and a lot more options and speed).