You could use a microcontroller that has built in EEPROM. The 8-bit PIC16F84A has 64 bytes of EEPROM, which is good for typically 10,000,000 and a minimum of 1,000,000 writes to each byte (this is known as byte endurance). The PIC chosen in another answer, PIC12F635 has a 128 byte EEPROM and a byte endurance of 100,000 writes. The PIC24F16KA102, a 16-bit processor, has 512 bytes of EEPROM and also a byte endurance of 100,000 writes.
The OP doesn't indicate how often the LED will blink. For the purposes of this discussion, lets assume it is four times a minute.
In one year it will blink
$$4 * 60 * 24 * 365 = 2,102,400\space times.$$
Since the EEPROM needs to capture both last the on and off events, then it will be written to twice that number, or about 4.2 million times. In five years, this is 21 million times.
Clearly, this will exceed the specs of any EEPROM that I now of built into a microcontroller.
But there is a simple solution for this. Instead of using the same byte over and over to keep track of the on or off status, one can use an array of bytes, which fill up the entire chip.
You need two bytes for each element in the array. So a 64 byte EEPROM, like the one in the PIC16F84A, could hold 32 elements. Each time you write to the EEPROM, you write a 0 to the status byte (meaning this element has data), and either a 0 to the data byte (LED was last off) or a 0xFF (LED was last on). The next time you access the EEPROM, you index through the elements until you find one with a 0xFF status byte, and then use the that element. If there are none left, then re-initialize the EEPROM and start over (for the low-end PICs, this means writing 0xFF's to each of the status bytes; for the PIC24, there is a command to erase the whole EEPROM). If you need to know the last status of the LED, you index through the array as before, but now go back one element and read out the data byte.
This essentially divides the number of accesses to a single byte by a factor of 16 for the PIC16F84A (16 and not 32 because each of the status bytes is written to twice). So it would be able to handle 16 million writes total, enough for almost four years of data. And the PIC12F635 with its larger EEPROM but smaller byte endurance of 100K, would be able to handle 3.2 million writes total, enough for nine months.
The PIC24F16KA102, with its 512 byte EEPROM and bulk erase feature, would be able to handle 25.6 million writes, enough for over five years.
If the blinking rate was only four times per hour instead of four times per minute, then this means a total of 70,080 writes per year. Even the PIC12F635, with its endurance of 100,000 writes per byte, would last would last 45 years!