Can Arduino operate under water?
There is at least one project in progress to create a dive computer using an Arduino. What the question describes is considerably less ambitious. 

Hence, yes, it is feasible to use a suitably enclosed Arduino for such a toy submarine. 

The challenges will be:


Watertight casing, yet which can be opened when needed: Silicone caulking will probably not survive under pressure and with salt water. Silicone gaskets on a torque-bolted enclosure will work though.
Interaction without having to open the case every time: If inputs are needed at all, innovative approaches such as hall switches need to be considered. See this answer for ideas.
Access ports: If programming or power connections need to reach the Arduino without taking it out of the case, pressure- and water-sealed cable ports will be needed in the enclosure. This is best avoided if at all possible.


Consider wireless programming such as through a ZigBee shield, to reduce the number of times the enclosure needs to be opened, and the number of access ports needed. 
Charging batteries will be an issue, wireless charging is still in its infancy - this may require opening the enclosure anyway.

Pressure: Depending on the depths being considered, the pressure the enclosure can stand will become a concern. For "toy submarine" depths, this should be a non-issue.
Humidity and salt: No matter how carefully the system is designed, oxide formation and leakage currents due to humidity + saline deposition will be an issue at some point. 


To add one additional level of protection, consider DIY or professional conformal coating on the Arduino, just in case the enclosure some day springs a leak or suffers condensation internally.
Also consider using a Ruggeduino or similar ruggedized board, for just that extra bit of survivability. 



Many Arduino enthusiasts would be very keen to know how this project progresses, so do keep us posted.