I would like to explicitly remove songs that I uploaded using iTunes Match, from the cloud. How is this done? And if I do remove the song, will it be automatically removed from all my devices?
According to this support article from Apple, you have to delete it from your iTunes library and then it will prompt you to delete it from iCloud/iTunes Match as well. I don't know yet if there's a way to delete it from iCloud while keeping it in your iTunes library.
It does appear, if you follow these instructions, that it does automatically disappear from any iOS device set up with the same iTunes Match account.
After a while I figured out how to do this.
You just press alt+Backspace while selecting a song and a windows pops up. Here you can mark the checkbox to remove the song from iCloud.
Apparently, there is no way to remove it from iCloud and keep it in your library, though.