First of all, I don't want to spam the Blockchain, I just want to learn more about this option.

Which wallets allow the user to record a message on the Blockchain?
Does the message has to be in Hex?

Thanks