Methods and apparatus related to message compression/decompression are described. A compressed message is generated by indicating what changes are to be made to a previous message to produce the message sought to be transmitted. The required change, in the form of at least one command and corresponding parameter, is transmitted as a compressed version of the message being communicated. This approach takes advantage of the fact that messages sent over time often include much of the same message content and only one or a few fields may have changed. The techniques are general and involve including a command in the compressed message along with at least one parameter. The command indicates processing to be performed on a previous message to generate the uncompressed message. The parameter may be, e.g., data to be inserted into the previous message or specify a location in the previous message where the change is to be made.