I'll second the vote on the easydriver - I'm currently using 3 on my project.
As madworm pointed out, you really don't need any special voltage regulation, the driver chip will do it for you.
For example, I run two arduinos and three stepper motors (rated @ 6v/0.8A each) off one 12v/3A power supply. I used the easydriver's current adjustment to tune down the motors to the exact amount of current necessary (well below the actual 800mA, which the easydriver cannot provide -- it's limited to 750mA, IIRC) to drive the load that each needs.
Be warned, the chips on the easydrivers can get quite hot, make sure to account for any ventilation needs.