Based on stuff on the web (Wikipedia and others) the GPS navigation message bit rate is 50 bit/s. That includes all data needed for user position calculation (time, ephemeris, almanac, etc.) It seems that the packet from a satellite should be much longer than 50 bits, so a complete packet must take longer than one second to completely broadcast (with a 50 bit/s rate.)
How is a 10 Hz position update rate (update each 100 milliseconds) possible?
50 bps is indeed the bitrate at which the almanacs and ephemerides are transmitted. Given the size of this data as well as framing and other overhead, it takes far more than 0.1 seconds (and more than 1 sec) to transmit this data.
However, the actual position calculation is done using precise timing information derived from the PRN, and that's coming in at the chip rate (1.023 Mchip/second for L1 coarse acquisition (C/A) code), rather than at the 50 bps nav rate.
The PRN repeats once every millisecond (for L1 C/A) so even the most crude cross-correlation with the PRN could produce a new (noisy) timing measurement at 1 kHz. A lower rate like 10 Hz allows more time for measurement, filtering, and calculation (see analysis here)
A new set of ephemerides is not needed for each position update; in fact a single ephemeris is valid for hours [ref here as well as pg.157 of here]. The GPS receiver continues making calculations with respect to the existing ephemeris, just using new timing information as it comes in.
The GPS receiver doesn't know where it is, nor where the satellites are. So it tries to lock on and decode the satellites that should be in view (based on the last known location which in this case is far off), but at the bitrate you mentioned it's a long process, 30 seconds if the receiver is currently decoding a satellite that's in view. The more parallel channels your receiver has and the more accurate you can provide an estimate of your current position (through Wifi/celltower triangulation), the quicker it will get a fix.
Some of the satellites which were previously tracked in the N channels of your receiver are still in view, or the time and location drift from the last shutdown were sufficiently small to use the last updated almanach (from internet or the satellites) to extrapolate which satellites are in sight now.
As nanofarad's said, the position is then calculated solely using the clock signals coming from the satellites - loosely said, they are corrected for Doppler shift and clock drifts, and the pulses are compared to triangulate the position of the receiver. See also this very informative link, of which these images are extracted.
(Note: In complement to nanofarad's answer)
