How does that "latch relay" business work for the on/off switch?
I used the Panasonic TQ2SA-L2-5V. You can switch it on and off with 5V.When you press the pushbutton the battery current switches it to on. The button press is also routed to an arduino pin, so I can use the pushbutton as an input (secret combination of timed presses to open the box). The relay's coil for switching it off is attached to an arduino output pin, so the arduino can switch it's own power off by putting that pin on high. It's pretty simple to build, I just added two diodes to the relay. I made some drawings on paper, but I think they aren't readable to anyone but me 
If you want something like this you could also buy the plololu switch. That does the same with solid state components but doesn't allow the pushbutton to be routed to the arduino (Pololu Pushbutton Power Switch SV (old version)).
So who is this for?
A work buddy of mine who is really into geocaching is turning 30 in two weeks. He'll get the box with his present inside.
The plan is, that he'll pass it on to another friend once he opened and reprogrammed it.
Every owner can log his experiences with the box on geocaching.com by using a geocode that is spray painted on the box (If you ever did geocaching: It's treated like a travebug - The groundspreak rules aren't allowing moving caches).
The url for tracking the box is: (TB3W7NC) TrackMe Geocoin - Rick's reverse geocache