I have always had my Nautiluscoins on exchanges (I know the dangers of doing this, but I actively trade any other coin except for Naut), and now I am storing them on my wallet. Total newbie question: How do I get my private keys? Do I need to write these down (probably multiple times) and save them in case I lose my wallet?
Just make a backup of your wallet.dat file on another computer/drive and you will be fine.
You can find that here (depending on OS):
Windows: %APPDATA%\Nautiluscoin\
Linux: ~/.nautiluscoin/
Mac: ~/Library/Application Support/Nautiluscoin/
Just copy it to a flash drive, external HD, etc. If you password protect your wallet, be sure to write down the password because it is non-recoverable.