How precise can I get Arduino using rotary encoders?
Interrupts are what you would use in this situation.

The rates that you have mentioned are slow enough where you probably would be able to count it inside of a loop, however this is not recommended, as a typical loop will take many clock cycles to complete, and depending on the number of instuctiuons per loop, you may miss some counts.

Interrupts are made for this purpose, as they can be triggered at any time, regardless of the state of the loop.

There is a function named attachInterrupt() which will take three arguments.


Interrupt Pin
Interrupt Service Routine
Mode


Below is an example for counting an interrupt

volatile int myCounter = 0;

void setup(){
    attachInterrupt(0, count, RISING);
}

void count(){
    myCounter++;
}


The Modes are as follows:


  LOW, CHANGE, RISING, FALLING


More information about using interrupts can be found here.

Depending on the encoder you use, you will need to tailor the code your needs, and do some more calculations to determine your position, but this should be a good starting point.

Edit
Here is some example code from Arduino Sandbox for using a rotary encoder.