How to remove Preview.app on-screen navigation toolbar?
You are going into 'Slide show' not full screen.

This maybe because you are using the wrong shortcut keys.

For Slide show:

cmd+shift+f

For full screen:

cmd+crtl+f