How to keep the signals at the pins on a Arduino upon software restart
I'm going to assume that the AVR controller on the Arduino board is similar to the Microchip PIC family in that the pins default to INPUT upon reset.

If that assumption is correct, all you need is a really simple sample-and-hold circuit for the relay driver.  It also requires you to think about how you have your software structured.  

First, I'll show the circuit.  Then I'll talk about the software implications.







simulate this circuit &ndash; Schematic created using CircuitLab

Software is really easy.

1) Controller is just coming out of reset.  Port pins are all currently set as Input.

2) Set port pin to desired level (Hi or Lo)

3) Change port pin(s) DDR to Output

Note that the above order is important if you want to avoid glitches.  If you set the pin to Output first, then set the level, there can be a glitch.

Also note that the circuit introduces a delay of about 1 ms.  I assume that is completely inconsequential if you are driving a relay.

You must choose a low-leakage capacitor for C1 but that's easy.  Tantalum works pretty good.