I was told that if I subscribe to spotify premium I would be able to download mp3s of all the songs they offer, however after signing up I can't find a "download" button anywhere. Was this just false advertising or an unsubstantiated rumour? How can I download mp3s from spotify?
You have never been able to download mp3s from Spotify.
Spotify is not a music purchasing service. It is a service for (effectively) renting access to music. Both the free (advertisement supported) and paid services rely on this model.
Spotify is a music streaming service which relies upon each track play being protected so that they cannot be freely copied. Otherwise a significant percentage of users would simply subscribe for one month, find and copy the songs they like and then only occasionally resubscribe to update their catalogue. This would not cover the costs associated with paying artists a fair price for their work. (Whether streaming services pay a "fair" price is a story for another day.)
What you can do is download the tracks (DRM protected) for use while you lack an internet connection. You are still subject to the restrictions of your subscription and the app occasionally verifying your rights to listen to the files when you have an internet connection.
If you want mp3 files then you will have to purchase the actual albums. Amazon allow you to download mp3 files of purchase tracks.