I know that I can use separate Apple ID's for iCloud and the App Store. However does this make them totally separate? In other words, if I am using different Apple ID's for iCloud and the App Store, will iCloud still be able to see the apps I download and will iCloud be able to see that I've logged into a different Apple ID for the App Store? (assuming I never backup my phone or restore a backup)
The logins are totally seperate. You can use one login for the app store and another for iCloud. There's no problems in that - iCloud wouldn't suddenly require the password for the App Store login or anything like that.