I believe the usual approach is to pass the message itself as plaintext, along with a cryptographic hash that serves as a signature and checksum.

A simple approach could rely on a shared secret passphrase to create an MD5 hash of the message. This is often more than good enough, and can be done using more robust hashes like SHA-1 instead.

HMAC describes a way of doing this that doesn't have the vulnerabilities of the simple approach. The process is described in text, symbolic notation, and in pseudocode.