Excuse me Henrik, If you read the spec. sheet you can set the interrupt edge for the INT0 and INT1. It is not required to set it each time. Also the interrupt routine look like:
Dave, I think you're misunderstanding what I'm saying.
The circuit you linked to is x1 decoder, effectively provoding 1/4 of the encoders available resolution. Your simply counting the individual lines of the A and B channels respectively. If that's enough, perfect go right ahead but if you need the full resolution of the encoder (as is the case here) then it's not going to cut it.

To use the full resolution of the encoder each and every edge of the two signals needs cause the counter the change up or down. If the encoder is connected directly to INT0 and INT1 it means that the edge causing the interrupt needs to changed on every interrupt so that it "catches" the falling edge after a rising edge etc. It's certainly doable if the PIC allows you to do it (not all do) but it does complicate things.

By using interrupt on change this is handled automatically because ANY change on ANY pin causes an interrupt so you will "catch" every edge (rising AND falling) automatically and you just need to decode the gray code in the ISR. From any given state (there's only four) you can only get to two other (valid) states, one is forward the other is backwards.

Look at this NI page on qudrature encoders, about half way down is a comparison of x1, x2 & x4 decoding.

/Henrik.