What are the key differences between different ways of embedding messages in the blockchain? Are some possible ways to embed messages in the blockchain better in some sense than others? What are the important differences?

(Followup on this answer)
There are multiple places one can embed messages in the block chain. Any field that takes arbitrary values can be used.


Nonce - nonce is a field in the header that can take 4 bytes of data. Not the best place to embed much, but it does not bloat the block size
Coinbase string - probably the best place to embed messages. It takes an arbitrary length and doesn't have to adhere to any rules. Main problem is that there is only one coinbase string per block, which usually means one would have to mine the block oneself in order to encode the string. Another important thing to note is that one should not use the exact same coinbase string all the time, as it might make the output irredeemable (if the transaction hash is duplicated)
Transaction outputs - The Tx message outputs can be used to encode messages in the form of output addresses and possibly Bitcoin transfer amounts. This can create irredeemable transactions (if the transfer amount is higher than 0). The overhead of encoding transactions in this way is not too big, in case of 0BTC transactions it would be 10 wasted bytes for about 23 bytes sent (total transaction size is about 33 bytes).
Transaction script - Probably the best way to encode messages, although it is not widely supported (requires custom transaction script creation). Messages are created by adding two script operations - OP_PushData and OP_Drop in the output script of any transaction, and adding the message body in between the two operations. In order to embed messages in this way one would add just a couple bytes in order to send fairly large body of text.


One could also try creating partial SHA collisions that would encode to some short message, although this method would require a lot of computing, yielding short message encoding.