It certainly sounds like relays are the answer. You should measure the motor coil resistance to get a estimate of the stall current. That will be the highest current pulled. My guess is 1A, 2 as most. If so, the relays will be cheap. For example I just pulled a DPDT relay from my parts bin. It rates 5A/30V and cost $1 each from one of the surplus suppliers. You can also check Ebay.
That URL you reference is a problematic design. Motors and relays have energized coils that can generate reverse voltage and burn out unprotected transistors. For a better choice see the ULN2803A darlington array with 8 outputs, which is frequently used with the Arduino. If the current draw is no more than 500mA you may not need the relays, just a single chip. The ULN2803A, protected by diodes, is designed for these applications.
See Adafruit at $1.95:
http://www.adafruit.com/products/970 (ULN2803A)
Joe