The connection between symmetries and conservation laws can be viewed through the lens of both Lagrangian and Hamiltonian mechanics. In the Lagrangian picture we have Noether's theorem. In the Hamiltonian picture we have the so-called "moment map." When we consider the same "symmetry" in both viewpoints, we get the exact same conserved quantities. Why is that?
I'll give an example. For a 2D particle moving in a central potential, the action is
$$S = \int dt \Bigl(\frac{m}{2} ( \dot q_1^2 + \dot q_2^2) - V(q_1^2 + q_2^2)\Bigr).$$
We can then consider the $SO(2)$ rotational symmetry that leaves this action invariant. When we vary the path by a infinitesimal time dependent rotation,
$$\delta q_1(t) = - \varepsilon(t) q_2(t)$$ $$\delta q_2(t) = \varepsilon(t) q_1(t)$$ we find that the change in the action is
$$\delta S = \int dt \Bigl( m ( \dot q_1 \delta \dot q_1 + \dot q_2 \delta \dot q_2) - \delta V \Bigr)$$ $$= \int dt m (q_1 \dot q_2 - q_2 \dot q_1)\dot \varepsilon(t)$$
As $\delta S = 0$ for tiny perturbations from the actual path of the particle, an integration by parts yields
$$\frac{d}{dt} (m q_1 \dot q_2 - m q_2 \dot q_1) = \frac{d}{dt}L = 0 $$ and angular momentum is conserved.
In the Hamiltonian picture, when we rotate points in phase space by $SO(2)$, we find that $L(q,p) = q_1 p_2 - q_2p_1$ remains constant under rotation. As the Hamiltonian is $H$, we have
$$\{ H, L\} = 0$$ implying that angular momentum is conserved under time evolution.
In the Lagrangian picture, our $SO(2)$ symmetry acted on paths in configuration space, while in the Hamiltonian picture our symmetry acted on points in phase space. Nevertheless, the conserved quantity from both is the same angular momentum. In other words, our small perturbation to the extremal path turned out to be the one found by taking the Poisson bracket with the derived conserved quantity:
$$\delta q_i = \varepsilon(t) \{ q_i, L \}$$
Is there a way to show this to be true in general, that the conserved quantity derived via Noether's theorem, when put into the Poisson bracket, re-generates the original symmetry? Is it even true in general? Is it only true for conserved quantities that are at most degree 2 polynomials?
Edit (Jan 23, 2019): A while ago I accepted QMechanic's answer, but since then I figured out a rather short proof that shows that, in the "Hamiltonian Lagrangian" framework, the conserved quantity does generate the original symmetry from Noether's theorem.
Say that $Q$ is a conserved quantity:
$$ \{ Q, H \} = 0. $$ Consider the following transformation parameterized by the tiny function $\varepsilon(t)$: $$ \delta q_i = \varepsilon(t)\frac{\partial Q}{\partial p_i} \\ \delta p_i = -\varepsilon(t)\frac{\partial Q}{\partial q_i} $$ Note that $\delta H = \varepsilon(t) \{ H, Q\} = 0$. We then have \begin{align*} \delta L &= \delta(p_i \dot q_i - H )\\ &= -\varepsilon\frac{\partial Q}{\partial q_i} \dot q_i - p_i \frac{d}{dt} \Big( \varepsilon\frac{\partial Q}{\partial p_i} \Big) \\ &= -\varepsilon\frac{\partial Q}{\partial q_i} \dot q_i - \dot p_i \varepsilon\frac{\partial Q}{\partial p_i} + \frac{d}{dt} \Big( \varepsilon p_i \frac{\partial Q}{\partial p_i}\Big) \\ &= - \varepsilon \dot Q + \frac{d}{dt} \Big( \varepsilon p_i \frac{\partial Q}{\partial p_i}\Big) \\ \end{align*}
(Note that we did not use the equations of motion yet.) Now, on stationary paths, $\delta S = 0$ for any tiny variation. For the above variation in particular, assuming $\varepsilon(t_1) = \varepsilon(t_2) = 0$,
$$ \delta S = -\int_{t_1}^{t_2} \varepsilon \dot Q dt $$
implying that $Q$ is conserved.
Therefore, $Q$ "generates" the very symmetry which you can use to derive its conservation law via Noether's theorem (as hoped).