(This is mostly copied from Chogath's item chapter because Chogath and Nautilus are very similar auto attacking tank machines and play fairly similar)
Standard jungle items, if a invade happens or you get harassed in a level 1 skirmish or you take damage during a gank, it's always good to have health potions top your HP off regardless of what champion you have. Nautilus has a shield to 'sustain' himself and is able farm fairly well past level 3 once his shield becomes tanky. The potions are mostly for if stuff goes wrong before level 4 as level 1 Titans Wrath is fairly weak as a shield so expect to use a few potions on your first clear or if invades and such happen.
Basic jungle items as we aren't interested in madred's razor. This gives you regen in addition to the fact that Nautilus isn't losing hp due to his shield so your hp is topped off for a gank between jungle camps. Boots allow Nautilus to roam the map faster and have less downtime between camps/ganks as he'll walk faster. Also strong in ganks where the enemy has yet to buy their own boots.
Spirit of the ancient golem is a very strong jungle item as it gives tenacity, cooldown reduction and HP for a nice price. The most important part in addition to the nice deal on stats is the tenacity which means we're allowed to go different boots (instead of merc treads all day every day). Ninja Tabi tends to be the safest as it scales all game and makes Nautilus very durable. Mobility is a slightly riskier solo queue style boots as it's useless late game but very strong at roaming and doing ganks early as it'll make Nautilus run extremely fast. If you can't get mobility early, I tend to skip it for Tabis or to get Tabis way later as you may also want to get another completed item before finishing the boots if you have a huge stash of gold on one of your buy back.
Next (get both unless support getting aegis, order is your choice):
You can pick which one to go for first but if teamfights are breaking out or if the enemy team has a heavy amount of Magic damage then I'd rush Aegis/Bulwark. This doesn't mean Locket is a bad item in those scenarios but Aegis does gives huge stats and is always active and it's stats don't level up as your champion levels like Locket does.
(get after spirit visage)
The reason for this choice is that sometimes the enemy has many auto attack champions or AD based champions (irelia,jax, most ADCs, Nocturne etc), a Frozen heart will be a better deal as it gives armor and helps your allies greatly as it slows the enemy attack speed just by being near the wearer (unlike the passive on Randuins which only affects the person hitting the target). Otherwise, Randuins is a better option for limited enemy physical attackers as it gives health in addition to armor to protect against the other forms of damage coming out. One advantage of Frozen heart is that it gives huge CDR.
Enemy has heavy magic damage:
(if no frozen heart) otherwise
Get spirit visage instead of randuins first if the enemy contains heavy Magic damage as you want to be maxed on cooldown reduction (40% is max) to have Naut spamming his CC and his shield (which will only have 0.8 seconds downtime). Abyssal will give nice damage to you and your team should you go that route (if you got a FH).