How to choose what voltage power supply to use?
It may be possible to use a 1.5v AA battery if you are able to find relays that operate at that voltage. Relays will be the most costly part of this setup, so I'd start searching for relays that you think would operate well for your purposes. The specifications and price on the relays should be the most important consideration in building this. You'll want to find them rated at very low voltage levels as well as having comparable closed switch resistance values to what is discussed in the articles.

Looking at some relays on digikey here:
http://www.digikey.com/product-search/en/relays/signal-relays-up-to-2-amps/1049448?k=relay
there seem to be many relays that have a Turn-On voltage between 1.05 and 1.5 V. If you get one of them, then you can choose your circuit to operate at that low of a level. In short, find a relay you like/have/can get cheap and then build the rest of your circuit around them.