AttachInterrupt() should do it, just like on any other Arduino...
yeah, Paul (of PJRC; author of the encoder library) writes nice, efficient, and clever code, but seems to be a bit careless about the idea of "easily portable/compatible to/with new platforms.") The interrupt code in the encoder library is ... really ugly.
I came across this in the documentation
Those are just the "normal" Arduino functions for those pins, aren't they? The Nano changes the form factor, but generally keeps most of the same functions on the same "Arduino pin numbers" as an Uno-like board...