The shield has power in for the motors. This can be at the same voltage that will run the arduino, but does not need to be.
You certainly do not want to power the motors through the arduino.
But both the arduino and the power in for the shield could be the same.
Have you looked at any of the tutorials for the arduino motor shield? It may not be the exact same as yours but it will get you closer to understanding how it all works.
First, thank you for your help. Can I have more of it?
I managed to get it to work.... almost.
I have a 9V battery which is powering my shield + Arduino. But the motor is just making some noise instead of rotating. I noticed that the motorshield only provides 2V to my motor (it needs 4.5V).
How can I achieve 4.5V? Do I need more input voltage?
You can use 12VDC but no more. If you have your stepper leads properly identified A+, A- B+ B- and 12VDC won't drive the motor it's likely the amperage the diver is providing isn't enough for your stepper. You can up the voltage but you will have to cut Pin 13 to the UNO or there's a good chance you will fry it. It might make more sense to look for a stepper that has lower amperage needs, Another idea is to look at AccelStepper.h and have the speed ramped up. Starting a motor from stopped can demand a lot more amperage than running it at speed.