Ok I've seen this misconception way too many times on either stonewall's videos and all over the forums and I had to comment. Change your pathing, Nautilus had the easiest time early game out of any tanky ap champion I've tried (other than the holy trinity of WW Nunu Fiddle). Press W at 1:47 so you have the most uptime and start on kruggs/toad smite immediatly. I was able to stay above 80% on all of the camps with naut even the chickens of death in a custom game without a leash.
Superior pathing from s1 is back in business boys (with a slight twist with the new smite rewards).
Oh and whatever you do, do not smite blue unless there's an immediate threat and you have to secure it.
runes: atk speed red, ap quint, armor yellow, cdr per lvl blue
masteries: 21 9 0 make sure you get the bladed armor, 3% health isn't worth it
You can play around with the masteries and whatnot but this seemed to be a good trade-off of faster clear/more damage on ganks and mid/lategame CDR with the scaling blues. You don't really need to be that tanky in masteries/runes if you can survive the jungle well enough without it because the juggernaut gives so much hp compared to old golem item's measly 200
Path: you can do anything... Easiest is Kruggs (smite) - chickens - Wolves - Toad (smite); back. (always over 80% on naut with this if you properly time your W)
If you need to secure buffs vs a counter jungler early: Kruggs/toad (get a leash) with smite; if you're on blue do it smiteless if red smite it for health; then do the small camp left in that side of the jungle, 1 small camp in the other side; do the buff; gank/do the last small camp or whatever you want. *note that this path is slower xp and money compared to doing small camps and upgrading machette.
I've jungled nautilus in s4 and this season the new jungle is an amazing improvement for him
Cheers