If you want to avoid the slow "boot" time of the Arduino and can afford a few micro-amps of power being consumed...
Connect the Arduino permanently to the power supply.
Connect a 100K resistor from pin 2 to +ve.
Connect your push button between pin 2 and ground.
Write code to put the Arduino into deep sleep and wake it up with an interrupt on pin 2.
Total current draw excluding any peripherals you connect will be less than about 40 micro-amps. (Double check the datasheet for AtMega328p-AU to be sure)
// SLEEP BROWNOUT DISABLE FOR AtMega328p
#define sleep_bod_disable() {uint8_t tempreg; __asm__ __volatile__("in %[tempreg], %[mcucr]" "\n\t" "ori %[tempreg], %[bods_bodse]" "\n\t" "out %[mcucr], %[tempreg]" "\n\t" "andi %[tempreg], %[not_bodse]" "\n\t" "out %[mcucr], %[tempreg]" : [tempreg] "=&d" (tempreg) : [mcucr] "I" _SFR_IO_ADDR(MCUCR), [bods_bodse] "i" (_BV(BODS) | _BV(BODSE)), [not_bodse] "i" (~_BV(BODSE)));}
/*****************************************************************************
SOMEWHERE IN YOUR CODE - This is where you want the MCU to go to sleep.
*****************************************************************************/
//Set up the interrupt on Arduino pin 2
attachInterrupt(0, SLEEP_ISR, LOW);
//Now put the device into deep sleep mode
cli(); // Turn off the global interupt
sleep_enable(); // Set sleep enable bit
sleep_bod_disable(); // Disable brown out detection during sleep. Saves more power
sei(); // Turn on the global interupt
power_all_disable(); //This shuts down ADC, TWI, SPI, Timers and USART
sleep_cpu(); // Sleep the CPU as per the mode set earlier(power down)
///////////////////////////////////////////////////////////////////////////////////////
//
// WHEN THE DEVICE WAKES UP - THIS IS THE ENTRY POINT
//
///////////////////////////////////////////////////////////////////////////////////////
sleep_disable(); // Wakes up and clears the sleep enable bit. Before this ISR would have executed
power_all_enable(); // This enables ADC, TWI, SPI, Timers and USART
delay(10); // This delay is required to allow CPU to stabilize
// CARRY ON IN YOUR CODE
/*****************************************************************************
The interrupt service routine for the sleep function
*****************************************************************************/
void SLEEP_ISR()
{
detachInterrupt(0);
}