The iPhone's backup does not include any iTunes content - music, movies, TV shows, podcasts, and 3rd party apps. All iTunes content on your iPhone including 3rd party apps should be in your iTunes library on your computer.
Sounds like you didn't have Sync Apps selected under the Apps tab for your iPhone sync preferences with iTunes. If this was selected, after downloading an app with your iPhone, the app will be copied to your iTunes library the first time you sync your iPhone with iTunes after doing so.
Having Sync Apps selected under the Apps tab for your iPhone sync preferences also provides for downloading an app with iTunes on your computer and installing the app on your iPhone when syncing. To remove an app from your iPhone, you can deselect the app under the Apps tab followed by a sync. To re-install the app on your iPhone at a later time, reselect the app under the Apps tab followed by a sync.
When restoring your iPhone with iTunes, your iPhone is completely erased first followed by the firmware being re-installed. After the firmware is re-installed, you have two options. Restore from the backup which is the default selection, or restore as a new iPhone or not from the iPhone's backup which must be manually selected. Either way this must be followed by a sync with iTunes to retransfer your selected iTunes content including 3rd party apps under the various tabs for your iPhone sync preferences - music, movies, TV shows, podcasts, and Apps.
This link provides the data included with your iPhone's backup.
http://support.apple.com/kb/HT1766
As already provided, you can re-download all apps with iTunes on your computer and you won't be charged again for a purchased app as long as you use the same iTunes account to re-download the app that was used to purchase the app originally. After doing so, select Sync Apps under the Apps tab for your iPhone sync preferences with iTunes followed by selecting the apps below that you want installed on your iPhone followed by a sync.
