Congrats on your new ride and indeed Xterra is a very good and capable 4x4.
I am not an Xterra owner, but my two cents are below:
Air filter alone doesn't make any fuel mileage difference unless accompanied with chip tuning.
Air filter just make it breath little freely and make you FEEL smoother of throttle response, at same as previous RPM.
Any major change in weight gain/reduction will make noticeable difference in fuel economy.
Any major change in vehicle geometry or aerodynamics make big difference - bullbar, roof rack, bigger lift etc.
35 kms gain per fuel tank could be the difference due to your driving habit or change to different route....?
You can compare your reading with other Xterra owners here: http://www.fuelly.com/car/nissan/xterra/2012