You probably got everything you need, but here's some background for you and people from teh future arriving here by search.
Check the voltage on the TX/RX lines, true RS232, such as the like that runs over DB-9 connectors on old-stylie computers use up to +15V for space (logic low) and down to -15V for mark (logic high), which is the opposite of what you'd expect. In fact the voltages are all silly, it's +3 to +15V for space, and -3 to -15V for mark, which is very likely to cause problems if you connect that to something that expects 5V TTL input (could also cause damage).
And that's the purpose of a a max232 circuit, as semicolo suggests. The MAX232 is a chip that converts this odd RS232 voltage levels down to 5V TTL (maybe even 3.3V, can't remember). You can also use discrete transistors and passives to do the same.
However, these days a lot of devices that have serial ports use RS232 but at lower voltages, specifically, they use +5V for space (which falls in the +3 to +15V range and is therefore a valid signal), and 0V for mark (which doesn't fall in the -3 to -15V, but is assumed that the computer is ok with this). This lets the device use 5V while TRANSMITTING to a computer, it does need a bit of protection from the <0V and >5V it would be RECEIVING from the computer, that could be as simple as resistors and clamp diodes.
+5V for space and 0V for mark is the wrong way round for proper TTL serial that a microcontroller usually deals with, but that can be easily inverted using a logic gate chip, or simple inverter circuit made of discrete and passives.
Therefore check the voltage on the TX pin of the GPS unit, if it's idle at <-3V, then you're dealing with a "true RS232" device, and you're going to need a rs232 transceiver like the MAX232 chip. If instead the TX line is idle at 0V, then you may be dealing with a "5V-level RS232" device, and you'll just need a simple inverter circuit to get it talking with an Arduino.
Just for comparison: TTL serial has the TX pin usually idling at +5V (or +3.3V if that's your logic high level). EXCEPT when the device is using hardware flow control and is sending a BREAK signal.