Having changed /etc/motd on my EC2 AMI only to find the original message upon the next spawn, I got annoyed and looked into making the change permanent, as I originally intended.
It turns out that the message of the day is generated by a script, namely /usr/sbin/update-motd. Further, the banner displayed is stored in /etc/update-motd.d/30-banner.
All I had to do now was edit this one file and let it be. Easy!