Well, I don't know about any intuitive explanation besides intuition gained by understanding the underlying math (mainly differential geometry, Hamiltonian mechanics and group theory). So with the risk of not giving you quite what you want, I'll try to approach the problem mathematically.
If you know Hamiltonian mechanics then the statement of the theorem is exceedingly simple. Assume we have a Hamiltonian $H$. To this there is associated a unique Hamiltonian flow (i.e. a one-parameter family of symplectomorphisms -- which is just a fancy name for diffeomorphisms preserving the symplectic structure) $\Phi_H(t)$ on the manifold. From the point of view of Lie theory, the flow is a group action and there exists its generator (which is a vector field) $V_H$ (this can also be obtained from $\omega(\cdot, V_H) = dH$ with $\omega$ being the symplectic form). Now, the completely same stuff can be written for some other function $A$, with generator $V_A$ and flow $\Phi_A(s)$. Think of this $A$ as some conserved quantity and of $\Phi_A(s)$ as a continuous family of symmetries.
Now, starting from Hamiltonian equation ${{\rm d} A \over {\rm d} t} = \left\{A,H\right\}$ we see that if $A$ Poisson-commutes with $H$ it is conserved. Now, this is not the end of the story. From the second paragraph it should be clear that $A$ and $H$ don't differ that much. Actually, what if we swapped them? Then we'd get ${{\rm d} H \over {\rm d} s} = \left\{H,A\right\}$. So we see that $A$ is constant along Hamiltonian flow (i.e. conserved) if and only if $H$ is constant along the symmetry flow (i.e. the physical laws are symmetric).
So much for why the stuff works. Now, how do we get from symmetries to conserved quantities? This actually isn't hard at all but requires some knowledge of differential geometry. Let's start with most simple example.
Translation
This is a symmetry such that $x \to x^\prime = x + a$. You can imagine that we move our coordinates along the $x$ direction. With $a$ being a parameter, this is a symmetry flow. If we differentiate with respect to this parameter, we'll get a vector field. Here it'll be $\partial_x$ (i.e. constant vector field aiming in the direction $x$). Now, what function on the symplectic manifold does it correspond to? Easy, it must be $p$ because by differentiating this we'll get a constant 1-form field $dp$ and then we have to use $\omega$ to get a vector field $\partial_x$.
Other way to see that it must be $p$: suppose you have a wave $\exp(ipx)$. Then $\partial_x \exp(ipx) = ip \exp(ipx)$ so momentum and partial derivatives are morally the same thing. Here we're of course exploiting the similarity between Fourier transform (which connects $x$ and $p$ images) and symplectic structure (which combines $x$ and $p$).
Rotation
Now onto something a bit harder. Suppose we have a flow
$$\pmatrix{x \cr y} \to \pmatrix{x' \cr y'}= \pmatrix{\cos(\phi) & \sin(\phi) \cr - \sin(\phi) & \cos(\phi)} \pmatrix {x \cr y} $$
This is of course a rotational flow. Here we'll get a field $y {\rm d}x - x {\rm d} y$ and the conserved quantity of the form $y p_x - x p_y$ which can in three dimensions be thought of as a third component of angular momentum $L_z$.
Note that the above was done mainly for illustrative purposes as we could have worked in polar coordinates and then it would be actually the same problem as the first one because we'd get the field $\partial_{\phi}$ and conserved quantity $p_{\phi}$ (which is angular momentum).
