and try to apply the solution with my Arduino Duemillanove and a unipolar stepper Teco 4H4018S2015 from my old scanner. I was glad to find the stepper's datasheet with the wiring diagram on the manufacturer's website:
However, I don't know how to connect the stepper to the ULN2003 and would therefore appreciate your help.
The second picture on there shows pretty much exactly what you need to do. You are going to have to adapt the wiring colors to your motor. On the left side replace the IBM-PC with Arduino.
But normally a stepper motor need a constant-current driver for proper operation, not a constant voltage. The motor will be weak especially at higher stepping rates.