itunes-match
As you probably already know, iTunes Match is a paid service provided by Apple.
With iTunes Match, all your music — even songs you’ve imported from CDs — can be stored in iCloud. So you can access your music from all your devices and listen to your entire library, wherever you are.
I was wondering the technology behind iTunes Match works. How does it match the songs on your computer with the right ones on the iTunes Store?
It keeps your custom metadata!
If you enable iTunes Match, your entire library (up to 25.000) songs will be synced with your iCloud. So all your songs are in the iCloud. You can add a device to the iCloud and by so, all your music on the new device will be synced onto the new device. That's how iTunes Match works.
If you computer/hard drive gets stolen, you buy a new one and authorize it with you iCloud, it will sync once again on your new device.
So yes, you'll be able to download all your music stored in your iCloud onto new device.
As a matter of fact, even when the original device lost it's files, the songs are still stored in iCloud.
But be aware, the limit on devices is set on 10. So make sure you haven't add 10 devices already!
EDIT:
Proof of this is on the iTunes Match-page
Best Answer
In late 2009, Apple bought LaLa.com, a site that did pretty much what present day iTunes Match does.
It analyzed tracks you already owned, and allowed you to stream the ones you already had on your hard drive.
The way the technology works is by analyzing the waveform of the music file and matching it to an existing database of known song digital audio fingerprints.
Obviously, that's way oversimplifying, but the basic idea of why you don't have to upload a lot of your library, as iTunes Match and formerly LaLa.com have an existing db of song "fingerprints."