How does one attach a message using a desktop wallet or cleos?
What is the max limit of the message?
How much does it cost to send a 1000 character message?
Answered here if you don't want to send EOS with your transaction, and here if sending EOS is acceptable.
What stops me from spamming the same message to every account and bloating the blockchain?
The mechanism by which EOSIO prevents spam is taxing you NET and CPU resources for transactions.
Do these messages get pruned?
Possibly. The whitepaper does mention as follows:
If the computational debt grows too large then, it becomes necessary to take snapshots of the blockchain's state and discard the blockchain's history.
However, this hasn't been necessary thus far, and you (or anyone else) can host all transactions forever if the resources permit. At the moment, the chain is about 30GB, and many BPs allocate a few TB for their machines, so it may not seem like an immediate problem. Worth noting, however, that once sidechains are available and if tens of thousands of transactions per second become common place, the growth of the chain may accelerate significantly.