Anything you retained you need to release it, if you only used the autorelease methods, you dont have to worry, but it is always a good idea to check for any leaks. I usually clean everything up on the onExit() inherited function and I also call this->removeAllChildrensWithCleanup(true); just to keep my mind clear.
If you use replaceScene method, your old scene will be gone, you will need to start another scene again when you use replaceScene. You can use pushScene and popScene methods, they keep your old scene on track. You can read about it more on the documentation, or see the code on test examples.
You need to worry about memory though, if your app takes too much memory on just one scene, pushing another might make your app use too much memory!
Replacing scenes gives you the option to release every node on the scene and also release any textures you loaded (using the caches singletons methods). This is usually good if your other scene uses another texture set and dont have (or dont need) anything related to the previous scene.
Always worry about memory! Always!