There's two ways you can go about this.
One is to use a dedicated watchdog chip - Maxim has a selection: http://www.maximintegrated.com/products/supervisors/watchdog/
The other is to use a second Arduino (or other small microcontroller) to act as a watchdog. Program it so that it expects some activity on a pin which resets a counter, and when that counter reaches a threshold it shuts off the power briefly to the master Arduino (which could be controlled by a P-FET, or a relay, or whatever method you like). The master Arduino then just has to ensure that it toggles the required IO pin regularly enough.