When you've enabled iTunes Match on your iPhone or iPod touch and your music has been deleted, it will be replaced by a list of the contents of your iTunes Match account. Now, when you go to the Music app, you'll see a small cloud icon next to each artist.
The cloud icon means that music by that artist is available via iTunes Match, but is not yet downloaded to your iPhone. The cloud icon disappears when you download the songs. But it's actually a little more complicated than that. To understand how, we have to go from the song level up to the artist level.
If you've downloaded all the songs from an album, the cloud icon next to the album name disappears, indicating that the album is on your device. If, however, you download some, but not all of the songs on the album, the cloud icon still shows up. This can be a bit confusing, but as long as the song doesn't have the cloud icon next to it, it's on your iPhone.
When you've downloaded all the music by a given artist from your iTunes Match account, the cloud icon next to the artist's name disappears. If, however you've download some, but not all, of that music, the cloud icon remains (just like with albums).
So, how do you download the songs, you may be asking? Proceed to the next step.