Electronic – How to correctly choose a memory

I'm trying to get an idea of what those on/off states may be. They shouldn't be mechanical switches; they maintain their state also when power is switched off. Unless you're afraid the may be toggled accidentally in transport. No memory can help you here: there's no electronic way to switch it back to the right state.
So the question is: what are those states and how are they currently controlled? They should be electrically or electronically controlled, or at least be able to control that way.

Let's look at the options you suggest:

1. the latching relay looks simple, but control-wise you'll have the same problem as with a microcontroller solution.
2. the EEPROM is the most logical choice to store settings, but it can't do anything on its own; it will need a microcontroller.
3. the CPLD. I find this a strange one, especially since it's much more complex to interface a CPLD to an EEPROM than it is for a microcontroller, and you mention expressly that you're a beginner.

Suppose one of the states is a transistor's. Could be a transistor that switches a relay, or switches an sound effect in a circuit. In any case, it must be used as a switch. You would read the state into a microcontroller, which stores it into nonvolatile memory at power-down. When the device is powered-up again, the controller would read the state from the nonvolatile memory and set the transistor accordingly. The original signal which controlled the transistor would have to be cut, otherwise it would conflict with the microcontroller's signal. So the microcontroller would also have to monitor this signal continuously and switch the transistor accordingly.

edit
the transistor may control just anything, like a relay. Low level audio signals can be switched by compact reed relays, which usually require less power.

Or you could use integrated electronic switches like the 74HC4066 and you may even not need the transistor.

The program for the microcontroller is easy, basically just copy an input pin to a corresponding output pin, and save to EEPROM. For the former you could use a CPLD , but like I said writing to EEPROM and reading from it is much more involved for a CPLD than for a microcontroller.
There are some microcontrollers which have on-chip EEPROM, like Atmel AVR, but you could also use an external serial EEPROM.

With the components that you have listed, you will not be able to build a system that will remember the state of a LED after power-off. The EEPROM that you listed can hold a value without any power, but the problem is that it has a (relatively) complex input/output protocol (I2C) compared to the other parts you have on hand.

I think you will find that there are very few methods for storing data that are both persistent while power is removed, and electrically simple enough that you could build it with the parts you have.

Given your requirements, a toggle switch is still probably the simplest method for storing a state, followed by some arrangement of latching relays.

If you wanted to store the LED state on the EEPROM you purchased, then the easiest way to interface with that device is to use a microcontroller. For example, you could get Texas Instrument's Launchpad board for around $5. But, many microcontrollers have built-in storage that would be more than adequate for storing the state of a LED.

You could "fake" your requirements by making a small, 1-bit memory cell (SR-Latch) and powering just the latch with a coin-cell battery. When you remove power, you would then only remove the power to the LED, not the SR latch, and this could last a long time. You would need to use low-current parts (CMOS), but this would be a very easy method as well.