iTunes Match is new (it arrived Monday) and exciting (all your music everywhere! your old CD rips upgraded to iTunes Plus quality!), but it's also confusing. What songs went where? Did iTunes Match find a track or did your copy of iTunes have to upload it to Apple's servers?
One way to cut through the confusion is by turning on a new view option in iTunes. Choose View -> View Options and check the iCloud Status box. This will add a new column to your iTunes list detailing the status of every item in your library.
(While you're there, make sure that iCloud Download is also checked--that column indicates whether a song is saved to your computer's hard drive or is only in the cloud, at which point a small button featuring a cloud and a downward-pointing arrow appears. You can download the file to your hard drive by clicking the button.)
Here's a first look at what those different iCloud Status messages mean.
Purchased This track was purchased from the iTunes Store by the Apple ID you've associated with iTunes Match. This is a status that's somewhat based on Apple's knowledge of your past purchases. Back in the day, I used to get around iTunes copy protection by burning iTunes-purchased music to an audio CD and then re-ripping it back into my iTunes library. I still have those files in my library, and many (but not all!) of them show up with a status of Purchased. I was able to delete those converted MP3 files from iTunes, click the iCloud Download button, and receive a new DRM-free 256-kbps AAC file. Instant upgrade.
Matched This track was scanned and matched to a song that's available in Apple's own database. If you didn't buy a song from Apple but you have the MP3 file--whether it was purchased somewhere else, ripped from a CD, or even pirated--it'll show up as Matched if it's in Apple's database. If you want to delete your track and re-download it from iCloud, you'll end up with a spankin' new 256-kbps AAC file.
Uploaded iTunes couldn't match your track with something in Apple's database. So instead, iTunes uploaded the file on your hard drive into iCloud. If you delete the track and re-download it, you'll get back the file you just deleted. There are no upgrades here.
Removed These are files you deleted from iCloud on one of your devices, but are still in the iTunes library on a different device. (The iCloud Download icon is also replaced by a sad cloud with a big "x" in the middle.) Here's an example: On my laptop, I select a live album and choose to delete it not just from the laptop but from iCloud entirely. When I switch to my desktop Mac, which still contains a copy of that album, its iCloud status changes to Removed. If you want to add those files back, just select them in iTunes, control-click on them, and choose Add To iCloud.
Waiting Somewhere, you added a track to an iTunes library, but that track hasn't yet been uploaded to iCloud. It shows up with the ghostly status of Waiting.
Not Eligible Some iTunes-compatible file formats are not allowed in iCloud at all. Digital Booklets, podcasts, bookmarks to Internet radio streams, and the like are marked Not Eligible. A few people on Twitter are reporting that low-bit-rate MP3s (perhaps below 96 kbps) are also considered ineligible for use in iCloud, though we haven't been able to confirm that.
Duplicate You've got more than one copy of this track in your library, so iTunes isn't going to waste its time trying to deal with it twice.
Error Something bad happened. On my Mac, this was a list made up entirely of tracks that I deleted from my hard drive but were still in my iTunes library.
With this in mind, you can figure out which of your tracks are a part of Apple's large database of music--and therefore potentially a quality upgrade waiting to happen--and which ones remain mysterious.