First things first, I already did a post on the 28BYJ-48 with a ULN2003 motor controller for the Arduino (HERE) and won't repeat the information listed there. If you are having trouble getting the motor to work on an ATtiny85/45, I recommend you go back and check out my other post. It has lots of useful links and tips.
If you need instructions on getting the ATtiny running with the Arduino IDE, check out my ATtiny label. For this post I will be using the Arduino Tiny core from Google Code. It runs on Arduino 1.5. For the programmer I will be using a USBtinyISP with my ATtiny85/45 programming adapter.
This really turned out to be pretty straight forward. Using the same Small_Stepper.ino example from my last post, I changed the pins to the correct values and everything worked (get my ATtiny sketch HERE). The motor turned nicely. One note about wiring, you can't actually wire this stepper the way that you define it. There are comments about this in my sketch, but for those that don't download the sketch, reverse the 2 middle wires. If you don't reverse the 2 middle wires the motor will not turn in reverse. If you want a longer explanation as to why and a complicated fix, go to THIS forum post. I just reversed the wires.
Example: Stepper small_stepper(STEPS, 0, 2, 1, 3); implies that you connect ATtiny pins 0, 2, 1, and 3 to pins IN1, IN2, IN3, and IN4 respectively. For this motor you should connect ATtiny pins 0, 1, 2, and 3 to pins IN1, IN2, IN3, and IN4 respectively.
Since that was so easy, I decided to do something else as well. I made a stepper version of the Knob example. Some readers may know that such an example already exists in the Arduino IDE, but I wasn't happy with the way it worked with my motor. My sketch works a little differently. As you can see from the video below, as I turn the knob, the speed of the stepper changes. If you want the sketch, you can get it HERE.
There you have it. Controlling a stepper motor with an ATtiny85 is not only possible, it is easy. If you run into problems or use this post to great success, let me know. I hope this post turns out to be somewhat useful.
-Matthew