Connect the relay coil across the input side of the regulator, using a series resistor if the voltage is too high. Then, switch your output using the relay contacts between the regulator output and the battery. When powered, the regulator gives you the output, if the relay de-energizes the contacts swap over and the battery produces the output.
You can monitor the output voltage using the Arduino ADC, if you want to tell whether AC or the battery is producing it, either use a second set of relay contacts if it has them, or use the ADC to monitor the voltage at the input of the regulator. If the output voltage is higher than the input voltage it means you are on battery power.
Brian.