How exactly does adding a new unit work in Cascade Correlation?
I've been reading up on cascade correlation quite a bit recently and made a python implementation https://github.com/DanielSlater/CascadeCorrelation (though it still needs a bit of cleaning up/extra work and has a bunch of me mucking around with using Particle Swarm Optimization for selecting candidates, definitely not production ready).

To try and explain step 3.


Start by creating a number of candidate hidden nodes with random weights. These have incoming connection from all existing hidden nodes and input nodes.
We then use that equation $$S=\sum_o \left | \sum_p(V_p - \overline{V})(E_{p,o} - \overline{E_o}) \right |$$ to train the candidate nodes. 
The residual output error is the difference between the output of the network and the target value(think sum of squared error without the square).
$S$ is the correlation between the activation of our candidate node and the the residual error.
$V_p$ is the activation of the candidate node given input $p$.
After a bit of backprop training against $S$ we choose our best candidate. This becomes a new hidden node.
This is when it's weights are frozen. That is to say after random initialization then back-prop training, then selecting the best one.