Beginners question: store data
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:  


the latching relay looks simple, but control-wise you'll have the same problem as with a microcontroller solution.   
the EEPROM is the most logical choice to store settings, but it can't do anything on its own; it will need a microcontroller.
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.