Methods and apparatus for compression of headers in broadcasting BCMCS services in a wireless communication system are described. Techniques used in BCMCS systems without feedback include sending static context information during BCMCS service initialization for use in a decompressor in a mobile station. Techniques used in BCMCS systems with feedback include receiving feedback from distributed mobile station decompressors and adjusting the broadcasting compressor in response to the feedback. Techniques that reduce the number of operating states in both the compressor and the decompressor are described. Techniques to classify flows so that a reduced number of contexts are used to compress/decompress session packet headers in a push-to-talk service are described.