In order to properly use your submarine to find the Nautilodestones, you will need to build a Magnetonomic Adjacency Detector. The detector requires a lot of esoteric parts, which are unfortunately out of stock in Dr. Nautilus's workshop. However, MIT, the Mechanistic Illuminatorium of Technocraft, has a lot of extra equipment lying around. You should be able to find all the necessary parts on MIT's campus.
Once you've done all of that, be sure to assemble your Magnetonomic Adjacency Detector before you get to the bottom of the ocean. Contact Sealab with a picture of your completed detector so that it can be verified.