Methods and apparatus for compressing messages used to support mobile communications are described. After transmission of a first mobile IP message which may be a conventional mobile IP message, a compressed mobile IP message is transmitted. The compressed message includes a new “compressed message” indicator and information which is to replace information in the previous message or to be added to the previous message to construct a new message. In some embodiments, the compressed message includes a mask field, e.g., a sequence of bits, each bit corresponding to one field of a standard registration request message or binding update message. If the mask flag bit corresponding to a field is set, it indicates that the compressed message includes information to replace the content in the corresponding field of the previous message or to be added to the previous message as a field corresponding to the asserted bit.