First of all they used curriers. A sometimes risky job, but a fine way to get your message from A to B without having to trust to many links.

Secondly, even though we sometimes think of old times as simple and primitive, they did have ways to either encrypt a message with code language, or have certain secret signs on letters and packages to let the recipient know, that this is not forgery.

Sealed letters were another way to make sure the message wasn’t tampered with or read.