For this autonomous rover I found that 16 steps would be the bare minimum, and easy to implement with common components.
As I didn't want to modify the RC car itself (drill holes, cut parts, etc), I looked for a solution that would minimize the impact on the car. As such I found that a good option would be to use the inner ring of the wheel as a surface for sticking an encoder band. This band has 16 steps, and looks like this:
