I looked into this briefly once. This is how I remember it:
The world map is divided into polygons, each of these polygons (or tiles if you prefer grid naming conventions) has its own terrain type. Each vehicle (including the player) has a set of terrain types it can traverse. I don't remember where the list of terrain types each vehicle can cross are. Sorry.
When it comes to the sub it works in a similar fashion. The sub is always over a tile in the "underworld" which is flagged as "can surface". If it is flagged as "can surface", it maps 1:1 with the deep ocean tiles on the overworld. The tiles in the deep ocean on the overworld are flagged as "can submerge". When the sub surfaces, it comes up to the corresponding tile on the overworld and vice versa. Extending where the sub can/can't surface or submerge would mean linking all new underworld tiles with the overworld tiles. I actually don't know how to do this.