From my research I know using 12V directly from the batteries is a bad idea given that they will be used to start the engine and such and I need to de-couple the power supply.
When you start the engine, the voltage may drop below 12V (perhaps below 5V). That's why your lights dim, if you have yoru lights on when you start your car. The drop in voltage may cause your Arduino to reset, which may, or may not, be a problem.
I have an Arduino in a vehicle, and I haven't actually noticed if it resets when I start the car. If it does, it's not a problem in my application. Once the car is running, I never get a "glitch".
There is already a regulator on the Arduino board, but the regulator can only hold the voltage as long as there's enough voltage coming in (about 6V).
If resetting is a problem... a capacitor (1000uF or so) on the Arduino power input, with a diode to prevent the diode from discharging into the other stuff on the boat may help, depending on how long it takes to start the motor... But, the capacitor-charge will probably only last for a couple of seconds, so the best solution is probably a separate back-up battery (probably with diodes or something so that the Arduino can run off the main battery most of the time).