Garbled serial from GPS device
I looked up the datasheet and product specs for the GPS device. It says that the output is RS-232.
Note that RS-232 is NOT compatible with the Arduino levels. Arduino "talks and listens" at 5V or 3.3V depending on which board you're using.
So what you need is a RS-232-to-TTL converter. Now, TTL speaks Arduino. So Arduino will be able to understand that. So try using a MAX232 IC or a shield, whichever you're comfortable with.