1)Is pwm the way to go, if i want to ensure feedback control?
If you require variable speed it's about the only option, along with suitable external drive electronics (H-drive if you require bidirectional rotation) rated at the voltage and current requirement for your specific motor.
If you require just on and off for the motor, then simple digitalWrite commands work fine using suitably rated transistor to drive the motor.
In both cases neither provides for or uses feedback control. That would require a sensor on the motor so the arduino could count or measure the motor speed. Then you would have to write a control algorithm that would utilize the speed value to adjust speed output as required. PID control is one such control method and there are several libraries around about.
I'm not familiar with how aq rate table operates, but have you considered stepper motors?
2)What sort of motors can be controlled with a pwm signal?
most any DC single phase (2 wires) motor is usable
I don't need a very high duty motor, that can pull a huge amount of torque.
How much less then huge? rpm, torque, voltage and current are the main specifications used in selecting a motor, but that is your burden as only you know what the motor will be required to perform.
Here are two pages of motors: http://www.allelectronics.com/make-a-store/category/400/Motors/1.html
3)If i have to use feedback to control the motor rpm, what encoders should i buy?
Any sensor can be made to work. Some motors come with speed sensors already mounted. optical sensors used with slotted wheels are pretty simple to work with.
How will the choice of encoders and motor affect the accuracy of the rate table?
Accuracy of control has many variables including can or does the load presented to the motor change or is always fixed? I suspect that encoder would be the least limiting thing in the control hardware and software loop.
Lefty