How to connect a stepper motor with exactly 4 wires to Arduino?
Your motor is Bi-polar. It has two windings and you need to use a circuit that constantly inverts the polarity of the supply to the coils.



This is done with an H-bridge that operates as four switches. 



You need one H-bridge per coil, so you'll need two of them to control your stepper. 
In practice these switches are either mosfets or transistors.



Refer to the below articles for stepper motor driving:
http://www.8051projects.net/stepper-motor-interfacing/introduction.php
http://www.mcmanis.com/chuck/robotics/tutorial/h-bridge/