Neo 6M GPS module and said "figure it out". Cool, I love projects like this.
Also see our Raspberry Pi version!
There are 4 connections, TX, RX, VCC and Gnd. I connected TX of the module to pin 10 on the Arduino, Rx to Pin 11, VCC to 5v, and Gnd to Gnd.
I started with a simple SoftwareSerial demo to make sure I could read the module:
SoftwareSerial mySerial(10, 11); // RX, TX
// Open serial communications and wait for port to open:
Serial.println("uBlox Neo 6M");
// set the data rate for the SoftwareSerial port
void loop() // run over and over
Then I added Mikal Hart's TinyGPS Library and sample code. This converts all those NMEA messages into a readable format by stuffing the character sequences into variables.
After a bit of massaging, here is the final result:
I still have more work to do, like displaying selected data on a LCD, but now that the data is in variables, that's easy. See http://arduinotronics.blogspot.com/2014/03/gps-on-lcd.html