You don't have to have an Internet connection to run NTP on Linux (ntpd). ntpd can get a time reference from two kinds of sources. The first kind, which is the way most people with desktop Linux machines probably use, is some other server that is accessed over a network connection (local or Internet). The second kind is an external piece of hardware that is directly connected to the machine running ntpd: a GPS/GLONASS receiver, a WWV/DCF77 receiver, an atomic clock, etc. This second kind is less common, but is how all the public time servers eventually derive their time.
As I understand it, the way ntpd does it on Linux, the 1PPS output from the GPS receiver is connected to one of the flow control lines on the serial port. When the 1PPS output goes high, the kernel is able to report the time it went high to ntpd. ntpd compares that timestamp to the previous one to decide if the system clock is running fast or slow, and steers the system clock accordingly.
The NMEA data from the GPS receiver comes through the "normal" RxD line on the serial port, and gets parsed to find out *which* second of the day it is. The reference for *when* the second starts is the 1PPS signal.
Most GPS modules will have some specification about how soon the NMEA data starts being transmitted after the 1PPS pulse, but as you noted, it takes time to receive and parse the NMEA data. This extra time probably doesn't make any difference if all you want is 1-second or so accuracy, but if you need finer resolution than that, you need to watch for the 1PPS signal.
If you are playing this game, you should also know about leap seconds. Basically, there is an offset between the time the GPS satellites report and UTC, currently 16 seconds. The current offset is transmitted in the GPS data stream, so it is possible for a GPS receiver to give you GPS time or UTC time; you have to pay attention to which one you are asking for and/or getting.
Every so often, this offset is increased by 1 second. Once every couple of years, the time as reported by a GPS receiver in NMEA will count
23:59:58, 23:59:59, 23:59:60, 00:00:00. If your parser isn't set up to accept 60 as a valid second, or if you've implemented your own clock- steering algorithm based on GPS data, your software can get very confused very fast. (It's also possible for there to be a negative leap second, which I think is done by skipping 23:59:59, but I don't think this has happened since GPS service started.)Matt Roberds