Ah, san Google... 
L'unica cosa che posso dirti è che ti serve la Mega perché è l'unica ad avere abbastanza interrupt...
P.S. ATTENZIONE ALLE TENSIONI!!! Arduino accetta tensioni fra 0 e 5V, se è un encoder 24V push-pull o PNP (cerca info su google) se ci metti un circuito per abbassare la tensione (che otrebbe essere un comune partitore resistivo) lo bruci...
Se il tuo encoder non è push-pull devi prevedere delle resistenze di pull-up se è del tipo NPN o di pull-dowm se è di tipo PNP. Anche per questo cerca su google, ci sono miliardi di discussioni in merito...