Your requirements are too fuzzy, but that said:
Any serial display will do but you have to know what you want to display on it. I think
-- LAT -- LON,
-- TEMP -- DEPTH (current and average?)
-- TIME -- DATE
In short a 4 x20 display would be nice => Parallax serial-interface 4x20 (#27979)
For logging I would use a - http://www.adafruit.com/index.php?main_page=product_info&products_id=243 - one of my favorites as it also has a RTC onboard.
If you have a laptop connected continuously you could send all measurements directly to the laptop of course (no need for a logshield)
? no idea ? what depths are you thinking 10meter 100 1000 more?
Almost any temp sensor will do but you have to take care of a isolation (salt water is more agressive). Dow deep you want to measure the temp? surface 1 meter mmore? Place the temp sensor in an stainless tube?
Maybe you should buy one a handdevice with serial out. for when you encounter an island on your journeys :)
Connect the GPS to the hardware serial port of the arduino
Connect the serial display with the New Soft Serial lib to any pin
For temperature the DS18B20 is quite good -
For depth ??
And maybe use a potmeter on an analog port to adjust the sample frequency. Note there might be a difference between the sample frequency and the log frequency. E.g. you might sample every second, but only log the average every 10 seconds.
Hopes this helps to get you started