I have no idea what makes Leonardo different from the Uno, I've only ever used Uno's.  I actually usually use a Pi where I can but for the CNC project I think an Arduino will work better and be more stable.  I need to do some research on the differences.

* Maybe only more pins?

Have a look at the Easy Driver (750mA max current), or Big Easy Driver (2A max current). They're good starting points for stepper control. You just hook up two pins (STEP and DIRECTION, plus common ground) and you're good to go.

You can get the easy driver on ebay for about $1.50, and then Big Easy Driver for about $5. Or, as it's you, Sparkfun (or is it Adafruit?) do them for about $30.

Pretty sure this is the motor shield I have, will it work?

Ish. That board will run 1 2amp stepper, but you'll struggle to get any decent speed out of the motor with only 12v to play with.

With steppers, voltage means faster coil switching (the time taken to change the the magnetic state of each coil, more voltage = faster change).

I'm aiming to use 24v or 36v to start with (either 2 or 3 atx power supplies wired in series :D )

Check out these: http://www.schmalzhaus.com/BigEasyDriver/

So one driver per motor?  What do you think of this one?

They're great (although that seems pricey, I got mine for about £1.5 each. I got a bunch and they're so cheap I didn't even mind when I let the magic smoke out of one).

They will only provide 750mA max, though (and ideally you want some cooling to run at that level for a long period).

Stepper motors:

More current = more torque.
More voltage = more RPMs.

The motors I ordered are rated for 4.5/5 amps, but when I ran them on my 750mA drivers they were still pretty strong. Don't think that'd hold up to machining, though, as I could stall them with a pair of pliers pretty easily.