Underwater is an incredibly challenging environment to try and build robots for- I have participated in the Marine Advanced Technology Education ROV competition for the past two years; here are a few quick things I have learned to keep in mind:
*Most commercial "waterproof" servos are really just water resistant, and have no depth rating. Actuating your robot at depth will be difficult, as many common waterproofing techniques for servos have some negative consequences. A walking robot
can be done, but there are reasons we don't see them wandering the ocean floor right now... mud and actuation
*Professional waterproof connectors (for cables and electronics) are a lifesaver, and will save you a lot of frustration in the long run.
*Once you are set with a final design for an electrical component, "potting" it by encasing it in a layer of epoxy (the two part kind you use on bar tops actually works great) will ensure that it is entirely waterproof/shockproof at the expense of not being able to make modifications to it.
*Bilge pumps make great underwater motors. Usually you can cut away most of the housing and the impeller; this gives you a waterproof DC motor ready to go. I recommend SeaSense 1100GPH as a good compromise between price and power. I can dig up the specs on it if you want.
*Macdad and propertyco are totally right about the tether. Being able to fish out your robot is a must. Not to mention most wireless signals degrade incredible quickly under water so that isn't an option.
*There are a few people on this forum that are experienced on this subject. If you have questions, try JonHylands, Admin, or madsci1016. They all do work with underwater robots on a regular basis, and may be able to offer expert advice.
BTW I love the video!