The frequency of the encoder signals is directly related to encoder resolution and the motor shaft speed (before the gearbox since this is where it is attached).
$$f_{enc} = CPR * u_M$$
where: \$f_{enc}\$ is the encoder output frequency, \$CPR\$ stands for "Counts Per Revolution", \$u_M\$ is the motor speed in \$\frac{revolutions}{sec}\$.
The Nyquist rate dictates the sampling frequency needs to be double the signal frequency. Note however that the two signals are offset by \$90^o\$ so it is like sampling a signal with a frequency \$2f_{enc}\$. Thus, the μC must use a sampling frequency of:
$$F_s = 4f_{enc} = 4 * CPR * u_M$$
This would be a minimum value and anything higher than that would be more robust.
The sampling frequency of the arduino, and any other microcotnroller, will depend on how fast your code is and the μC clock. For this specific application, you can use one of the encoder outputs as an interrupt signal and when the interrupt is triggered, you just read the second output. Then, just increment or decrement the counter according to the value of the second output. This is much faster than continuously sampling the signals. Although it is non-deterministic since the code now involves an interrupt.
The encoder "datasheet" is so bad I can't tell what the CPR is but once you get that value, computing the minimum required sampling frequency is straightforward.
