The pin connection layout is this:
GPS RX -> Arduino digital 4 (D4)
GPS TX -> Arduino digital 3 (D3)
GPS GND -> Arduino GND
GPS VCC -> Arduino 5V
It took a while to get a fix (find a satellite) but after it had, I received this over the serial port!:
EDIT 15/04/15:Just took the module and Arduino out for a drive in the car and then plotted all the points (about 500 of them) on a map - I am very pleased with the results.