Adding encoders to existing stepper system?

Thanks for all the help so far, guys!

I've managed to sort out the problem of the random-steps that my
board was receiving - it turned out to be coming from my PC. When I
cut with my laptop I have no problems at all. I think this is because
of the sherline motor inducing spikes onto earth. The notebook is
obviously a bit more well protected from spikes and glitches.

Anyway, I am still having a few problems with my sherline. Once in a
while (and in specific places on my X/Y axis) I hear the motors make
a nice clacking sound as they move - in the middle of their movement,
this tells me that they're losing steps! The motor must be bouncing
to the next stepper position and missing out a few. It doesn't do
this too much, just now and again.. I guess there are tight spots on
the X/Y travel.

To cut to the chase: I'd like to add encoders to my axis. It seems
that these little bounces here and there don't affect small
operations, but since it's all cummalative, it's obvious that over
time (and especially on larger jobs) they'll add up until my work it
out of tolerances. Fortunately, I have double-ended motors so there's
somewhere to mount the encoders easily.

I was wondering the following: how many steps/rev do I need for
encoders? Do I absoloutely have to have encoders with more steps than
the motor? If I had the same number of steps in the encoder as the
stepper, wouldn't the small differences in their "phase" cause the
motor to endlessly dwindle between the two positons? Can I use an
encoder with _LESS_ steps than the motor? I've seen many 50ppr
encoders for quite cheap - that's work out to 1/50mm on my sherline..
something I'd be more than happy with.

Finally, what software to use? At the moment I'm using TurboCNC, but
EMC does look quite appealing (especially the price :) )

Once again, I'm indebted to your good advice.