I've tried a lot of solutions to prevent Nautilus from auto starting when I initiate a KDE session and I've found this one to work fine:
1 - Go to Ksysguard and kill any instance of nautilus still running (or killall -9 nautilus from a terminal)
2 - In the application launcher edit nautilus and change the launch command to: /usr/bin/nautilus --no-desktop
From then on Nautilus won't auto start again when you start a new session. I suspect this will work on other environments (xfce, etc), the important bit is launching Nautilus with the "--no-desktop" flag.
Hope this will help you get rid of this annoying "feature"