There are basically 3 parts to the GPS signal:
- A satellite ID (called the Pseudo Random Code)
- Almanac data (orbital information for all the satellites)
- Ephemeris data (the orbital information for the single satellite in question, including the very precise clock information necessary to calculate the distance)
Basically, the almanac enables the receiver to know which satellites to search for. It tells which SHOULD be in sight at this point, but obviously something may block line of sight to it. But before ephemeris data has been received for at least 3 satellites, a (2D) position cannot be given. That data is broadcast every 30 seconds.
The receiver may cache almanac information but ephemeris data cannot be cached for long (due to clock drift, mainly), so waiting for reception of fresh ephemeris data is generally what's causing the startup time on GPS receivers.