The compressor assigns "connection numbers" to TCP/IP connections. The compressor and decompressor use these as indexes into a state table to construct the compressed headers and reconstruct the full headers.
The compression operates at the level of individual point to point links, it sits below the IP layer but above the link level framing. When a packet comes in over a link using header compression it will reconstruct the full header before making any routing descisions. If the outgoing interface also uses header compression it will then attempt to recompress the header.
Due to separate state tables a packet may be compressible on the incoming interface but not the outgoing interface or vice-versa.