Since all GPS's output NMEA sentences and often for our projects we need to extract the actual data from them, we've simplified the task tremendously when using the Adafruit GPS library. By having the library read, store and parse the data in a background interrupt it becomes trivial to query the library and get the latest updated information without any icky parsing work.
Open up the File→Examples→Adafruit_GPS→parsing sketch and upload it to the Arduino. Then open up the serial monitor.
In this sketch, we call GPS.read() constantly in the main loop (if you can, get this to run once a millisecond in an interrupt). Then in the main loop we can ask if a new chunk of data has been received by calling GPS.newNMEAreceived(), if this returns true then we can ask the library to parse that data with GPS.parse(GPS.lastNMEA()).
We do have to keep querying and parsing in the main loop - its not possible to do this in an interrupt because then we'd be dropping GPS data by accident.
Once data is parsed, we can just ask for data from the library like GPS.day, GPS.month and GPS.year for the current date. GPS.fix will be 1 if there is a fix, 0 if there is none. If we have a fix then we can ask for GPS.latitude, GPS.longitude, GPS.speed (in knots, not mph or k/hr!), GPS.angle, GPS.altitude (in centimeters) and GPS.satellites (number of satellites)
This should make it much easier to have location-based projects. We suggest keeping the update rate at 1Hz and request that the GPS only output RMC and GGA as the parser does not keep track of other data anyways.