I have been looking into this myself. After getting some advice online I have come up with this circuit :
The top left power source is the mains supply and the bottom left is the battery.
A voltage divider is connected to both that then feeds into an OPAMP comparator. For illustrative purposes there is a switch at the top left you can toggle to see the circuit in action.
When the mains power gets cut off the op amp comparator sends a logic level signal through the diode and into the mosfet which enables the battery circuit. the capacitor is there to keep power while the comparator makes the switch.
The link on every circuit is interactive, so feel free to have a play about with it. The LED represents your Arduino. The OpAmp is powered by the Positive and negative rails of thi diagram (impossible to draw on EveryCircuit)
Be sure to attach a voltage regulator to this circuit (at the input of the Arduino) so that the voltage doesn't change to your Arduino.
Here's where I researched about comparator OPAMPS ... Setting up a comparator OpAmp circuit
The LM358 is a good very cheap OPAMP for this circuit. All parts well sourced will cost you about £1 (or less).
Or if your battery is rechargeable you can try this circuit :
Again this is just for illustrative purposes. You will need a 5V step-up converter to get 5v from a 3.7v battery. Also the battery I am using has a builtin protection circuit, if yours doesn't it's important you include it in your schematic.
Here's a video of it working for me with a 3.7V Li-Polymer Battery: