Why does maneuvering speed vary with weight?
At the normal stall speeds given by $V_s$, the load on the aircraft is 1g, and the lift is equal to weight. i.e $L = W$.

In case of maneuvering, the load factor is greater than one, and we have $L = nW$, with $n$ being the load factor.

We have,  $L = nW = \frac{1}{2}  C_L  \rho  V^2 S$.

This gives maneuvering speed , $V_a$ = $V_s \sqrt{n}$ 

It can also be written as $V_s$ = $\sqrt{\frac{2 n W}{\rho C_{Lmax} S}}$

At maximum weight, this gives, 
$V_A$ = $\sqrt{\frac{2 n W_{max}}{\rho C_Lmax S}}$

For other weights, we have,
$V_a$ = $\sqrt{\frac{2 n W_{a}}{\rho C_Lmax S}}$

For the same load factor, we then have,
$V_{a} = V_{A} \sqrt{\frac{W_{a}}{W_{max}}}$,
where
$V_{a}$ is the maneuvering speed at weight $W_{a}$ and $V_{A}$ is the maneuvering speed at maximum weight $W_{max}$

As the maneuvering speed depends on the load factor and the stall speed, it depends on the weight of the aircraft (which decides the stall speed). It is basically a structural limit.

Another thing to note is that the aircraft can sustain structural failure even below maneuvering speed when multiple large control inputs are given.