Thanks. After digging into the FAQ there, the answer is that the data is stored in the 'OP_RETURN' code of an unspendable transaction. (Although some bitcoin is still spent on processing the transaction.)

The OP_RETURN code was introduced by the Bitcoin core developers to address (but not necessarily endorse) the increasing desire of people to store non-financial data. The code signifies that an output is provably unspendable, allowing transactions to be pruned from the UTXO database.