They are moved out of outlook and into the iCloud data file on your computer then synced with the cloud - but this data file is only accessible when it is open in outlook. If you sign out of iCloud on the computer, it offers you the chance to make a backup copy. If you sign in to the iCloud on another computer, you can link them to outlook on that computer too.
So the answer is they are stored locally, but you need the iCloud connected to outlook to get at them.
Diane, I didn't realize you had replied here. I just turned notifications on.
Thanks for the info. So are the contacts also stored in the cloud? If someone is using iCloud and Outlook, and their computer dies, when they get a new computer and connect to iCloud, will the contacts be downloaded from iCloud into the new Outlook installation?
Do you recommend backing up the iCloud data file?
Also, do you still recommend against using iCloud with Office 365?
Yes, contacts in the iCloud folders are stored in the 'cloud' and they'll sync back down when you sign in to the iCloud. You view them at anytime at iCloud.com or on your iDevices.
You don't need to back them up, but it's not a bad idea to do so, especially if you might do something stupid, like delete them from one of the devices. That will sync up and delete them from the server.
You don't need the iCloud with office 365 accounts as everything is in the cloud already. This applies to Exchange online, outlook.com, and gmail. (Although getting gmail to outlook is difficult and using the iCloud makes sense.)