From what I understand (reading through the forums and the net), the LCD not being serial, I'll need an arduino for sure on the LCD side, am I right?
You can buy a serial LCD and have longer cables (baudrate should be adapted), optionally use RS485
Questions:
1) Hooking up a GPS to a wireless makes sense? fast enough for the data? (GPRMC nmea data at 5hz?)
Arduino should be able to handle this, and that said, you can allways decide to send only 1 GPS sample per second to display as you cannot read all that info at 5Hz constantly. Furthermore it will not change that fast (unless your ship is a spaceship?

2) On the sensor side, it could be between 2 modems + 0 arduino and 1 modem + 1 arduino.
Think you do not need a modem.
Furthermore you need to check NewSoftSerial library and you can make multiple serial ports.
Along with the LCD display, I would also like to access the wireless data over a computer (pc or android)
Questions (cont.):
3) The big one; what kind of wireless protocol is best for what I am trying to do? (Xbee, Wifi, Bluetooth, Radio), I am getting a bit confused on what's available.
Have you though about wired ethernet on your boat? How much metal is there on your boat (blocks/influences wireless protocols.
hopes this helps,
Rob
Which country are you from?