Yes. You need to be using the same Apple ID on all the devices, and have set Automatic Downloads to on under Settings->iTunes & App Stores on all the devices.
If you are in a country that allows it, deleted purchases can be redownloaded from the stores at no extra cost.
iTunes in the Cloud and iTunes Match Availability
Purchases do not take up iCloud storage space.