The simple answer is in the EEPROM. Chose a PIC with EEPROM in it and store any data you want.
However, there is a significant problem with that. The EEPROM can only be written to a limited number of times, maybe 1 million times. If you store time every second, you would wear the EEPROM out after two weeks running. What you have to do is store the time only when the power is failing. You have to detect loss of power, but still have enough power remaining to run the PIC for long enough to store what readings you need in EEPROM.
Alternatively you can have a small battery or a big capacitor to keep the PIC going. When you loose power, put the PIC into sleep mode, and wake it when power is restored. Power consumption in sleep mode is virtually nothing, and all the values in RAM are kept.