iCloud backup will back up your data (game progress, app settings, photos in cameral roll, etc); it knows what apps & music you've purchased so it doesn't actually back those up but if you need to restore from iCloud backup it'll redownload those apps for you.
Basically, what counts against your storage is the data; the purchased apps and music don't count against your storage space as it'll just redownload fresh copies of those.
So a 20+GB phone may only hold 2-3 GB of actual data (likely even less) while everything else can be redownloaded.
Movies aren't included. Studios won't at this time allow re-downloads, so those should be backed up to your computer. Those don't seem to be backed up to your iCloud's storage space, either.
Music not purchased from iTunes doesn't get backed up to iCloud at this point, either, but will be coming more or less via "iTunes Match" later this month. For now, those will obviously be on your computer (right? Had to get on your phone somehow), so no need to back up those up to iCloud.
Personally, I'm doing both iCloud and Mac backups. This way if I destroy/lose my phone I can go to an Apple store or Verizon, get a replacement and have it up and running instantly with all, or nearly all, of my stuff ready for use. The remaining items (music not purchased from iTunes, movies) can then be added when I get home.