Well, there are a couple of ways. It could be a feature on a phone, where the phone stores and plays back your voice, just as it plays back a speed-dial number you would enter.

Or it could be a feature in the network, where if the network detects you pressing a key after answering, it sends your pre-recorded voice (or even theirs) to the caller, possibly also blocking the tone.

Finally, it could be made into a very tiny box that plugs into the standard headset jack. Today the box could be not much larger than a plug and battery. A button could trigger the messages. Or, perhaps easier to build as a project, it could be a feature on a bluetooth headset. Bluetooth headsets have a button to answer the call. They could have another button to answer and play a message pretty easily.