Unfortunately you did not provide a link to the data sheet of the encoder.
One physical step at the knob can generate changes on both pins. And since you have assigned the interrupt service routine to both pins, it is called two times for each physical step.
Another possible reason is "bouncing" of the mechanical contacts in this encoder. That means, that multiple pulses are generated on the change between open and closed. Therefore, change or edge interrupts are only a correct solution, if you take bouncing into account.
To investigate the issue, you can insert port pin toggles to your interrupt service routine. For example, set a pin on entry and reset it on exit. Then connect an oscilloscope or logic analyzer and compare the input signals and this output.
Oh, and it is never a good idea to put serial output in an interrupt service routine. Depending on the amount of sent data and the chosen baudrate, this output will block the routine for several milliseconds. During this time, the same interrupt is not serviced, and can be skipped in case of multiple triggers.