FPGAs are volatile devices so, yeah, it'll lose the program when you cycle the power. The board has a flash memory unit on it that you can program - at power-up, the FPGA will pull its program from there.
Hope that helps,
In Quartus, click File->Convert Programming File. This tool will allow you to re-target your .sof file (which programs the FPGA) to a .pof file (which will program the flash memory). Once you've created the .pof file, just use it in the Programmer like you currently use the .sof.
I'm afraid I'm not actually familiar with the specific board / flash device you are using so there's not too much more I can suggest here. Are you sure you've definitely used the correct device type in the tool and that Active Serial is the correct mode?
Did the tool give any actual warnings/errors apart from the "Failed"?
Your board probably doesn's support direct programming. The dev kit vendor should provide some guides on this. I have not done this in awhile, but most eeproms can be programmed using JTAG indirect mode which works just as well imo. The fpga configuration must have a JTAG programmer IP on it so the programmer can access the EEPROM chip from JTAG. Its sounds harder than it is. As I rember it, set the programmer to JTAG, clear any devices from programmer list, then add the POF file to the JTAG.
Quartus has a bunch of pre built SOF files for every device which will include the JTAG IP megafunction for programming purposes only. It has no other function.
So programmer will add the SOF and POF to the programmer list. So the process is, 1st program the SOF to get JTAG IP in the FPGA, then 2nd item should be a EEPROM device which will program the POF.
If the FPGA already has been programmed with a SOF that as the JTAG IP in it, then JTAG auto detecting button will show both the FPGA device and a EEPROM device listed as duaghter device EEPROM can be programed directly.
Does your EP4CE6 fpga board support Active Serial configuration mode? What is the configuration flash device part number that if connected to the EP4CE6 device? You need to understand which type of configuration scheme does your EP4CE6 fpga board support apart from JTAG. If your board does support Active Serial configuration mode together with JTAG mode then you should be to use the SFL (Serial Flash Loader) method to program the configuration flash with .jic file via JTAG mode.
You can check out the how to video here that shows the steps to generate and program the .jic:
For details about SFL (Serial Flash Loader), you can refer to AN370 in the following link: