Can you confirm if I'm on the right track here?
As far as I know, according to http://www.cocos2d-x.org/wiki/Data_Structures
use Vector<T> in place for deprecated __Array or CCArray.
use Map<T> in place for deprecated __Dictionary or CCDictionary.
use Value in place for deprecated __Integer, __String, etc
Is this right?
Also, what's the difference between __ and CC? xcode tells me CCArray, CCDictionary, etc are deprecated, but when I use __Array or __Dictionary, it doesn't.
yes you are in the right track. but make sure you don't confuse the cocos2d vector with std vectors. They are different. The link you have explains pretty much all you need to know about them
The term CC used to be applied before all the class names to indicate that they were part of Cocos2d. Infact if you look at the header files they still named CC. They changed the namings on these classes so they don't have CC in front of these clases anymore. I am not entirely sure why they had to make such changes but you might get errors here and there because of these changes if something else uses the same class name in your project. As long as if you use the namespaces you won't have trouble. for example instead of Vector you might need to do cocos2d::Vector to indicate you ment to use cocos2d vector instead of the std::vector.