Usually people don't use encoders with steppers. They are not needed for most stepper applications. However, having said that, there is a lot of work and discussion going on at the moment about using steppers with encoders to create unstallable (no lost step) stepper systems. Marriss is talking about 1000 count encoders (4000 counts quadrature).
However, when this is available it will require a different drive (i.e., a Gecko).
There are also some people working on just closing the loop on the stepper by feeding the encoder signal back into the PC so that lost steps would result in a system fault and stop the machining.
Take a look at the US Digital site to see the encoders that they have available. If you insist on encoders basically you have 4 factors to determine: (1) How many count?, (2) What size shaft are they going to mount to?, (3) What are the current limitations on the drive or board that they will be connected to, if any?, (4) Do you need an index pulse?