My name is NortheastPizza. I'm Silver IV so this build may not work in higher level play. I dunno, it works pretty well for me where I am now. I play on the NA server if you want to look me up. I've been playing since August 2012. That's about it.
Nautilus' combo must be done properly to be most effective and deadly. It's easy though, you'll learn it after you do it a couple times. Engage with your Q whenever there's an opening, then AA once, activate W immediately after for AA reset, then E. If you're 6, you ult somewhere in your combo, almost always at the end when they try to run.
Use whichever Reds you want to; none of them seem all that great to me so I personally use Flat AD just to poke a bit I suppose. As for your Blues, Take MR per level, usually there won't be strong Magic damage from your enemy bot lane and thus no need for high MR early on. My Quints and Yellows are gold generating because Nautilus always need gold.
Take Heal because you have plenty of CC already (Three of your abilities are CC, including your passive!) and clutch heals always feel nice, especially in a Team Fight ;)
You could take exhaust if you want though. Whatever works best in your game or playstyle.
Nautilus support used to not be viable because he needed gold. Now in S4 we have gold for days as supports, so why not play Nautilus?