Does the arduino card and stepper motor run on 12V with 800mA ?
Post links to the actual stepper motor and the motor driver, and someone will be able to tell you if they will work together.
Well, you are half-way there! That low voltage, high current motor requires a chopper-style motor driver, like those sold by Pololu.
Oh shit, I have been bought a too strong stepper motor. Thus, I must buy a new.