That's correct. A stepper is a very different type of motor. I think they are really awesome for what they do because other motors can't do what they do. Their strong points are absolute fine control and "holding torque". Generally they have 180 "steps" per rotation but with some advanced techniques you can "microstep" (more on that later).
A stepper motor has 4 leads coming out of it (sometimes they have more, but then you'll tie pairs of them together to reconfigure and you always end up with 4 leads to drive). The leads are in two pairs, A and B which corrospond to a pair of coils. If you drive both A and B with forward voltage the motor will snap to nearest forward-forward position. Then you can reverse polarity on A and it will snap to the nearest reverse-forward position. Then reverse B and it snaps to the nearest R-R position, then forward A again and you get to the nearest F-R position. You've just moved 4 steps of 180 and the motor has turned 8 degrees.
If I haven't lost you yet, that's the 4 possible combinations of forward/reverse polarity on A and B coils. To move in one direction you do this: FF, FR, RR, RF, FF, FR, RR, RF. To move in the other direction you do this: FF, RF, RR, FR, FF, RF, RR, FR.
At any time you can leave the coils charged as they are and the motor will hold still with a lot of torque. You can transition those "states" as quickly or slowly as you like and move forward and backward at your whim. These are why they are great for low-cost CNC machines.
To drive one with an Arduino you have two choices. First, you can learn how to use an "H-Bridge", which is a way of forward/reverse/off/short polarizing a coil using two arduino outputs (10 is forward, 01 is reverse, 00 is off, 11 is short). An H-Bridge is just 4 mosfets and you can google the configuration and usage. You'll need one for each coil.
The other way to drive them is with a specialized motor driver chip. We like to use A3977 by Allegro. These let you just use a Direction, Step, Enable and Sleep input and it does all the sequencing for you. This is where "microstepping" comes in. You can actually get a little finer than FF, FR, RR, etc... you can do FF, 80%F20%R, 20%F80%R, RR... this "steps" the motor between the regular locations and the Allegro chip takes care of all of that. This nets you up to 16 times the steps (depending on the chip, usually 8, SOME do 32) so you're now in the thousands of microsteps per rotation range. And THAT is why you'd want an stepper, so you can make good use of all that accuracy to do things like CNC or tracking camera or robotics. The encoder is used for feedback to make sure you aren't "cogging", or skipping from one FF position to the next because of external force, or not moving forward because of a blockage. If you try to go really fast against a torque load it will skip back to the previous cog and you don't know that unless you're reading an encoder.
The wikipedia page on steppers is actually a pretty precice read for you to get started.
No problem - we finally hit a topic that I have some solid input on