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).
Best Answer
In this answer let us for simplicity restrict to the case of a regular Legendre transformation in a point mechanical setting, cf. this related Phys.SE post. (Generalizations to field theory and gauge theory are in principle possible, with appropriate modifications of conclusions.)
On one hand, the action principle for a Hamiltonian system is given by the Hamiltonian action $$ S_H[q,p] ~:= \int \! dt ~ L_H(q,\dot{q},p,t).\tag{1} $$ Here $L_H$ is the so-called Hamiltonian Lagrangian $$ L_H(q,\dot{q},p,t) ~:=~\sum_{i=1}^n p_i \dot{q}^i - H(q,p,t). \tag{2} $$ In the Hamiltonian formulation there is a bijective correspondence between conserved quantities $Q_H$ and infinitesimal (vertical) quasi-symmetry transformations $\delta$, as showed in my Phys.SE answers here & here. It turns out that a quasi-symmetry transformation $\delta$ is a Hamiltonian vector field generated by a conserved quantity $Q_H$: $$ \delta z^I~=~ \{z^I,Q_H\}\varepsilon,\qquad I~\in~\{1, \ldots, 2n\}, \qquad \delta t~=~0,$$ $$ \delta q^i~=~\frac{\partial Q_H}{\partial p_i}\varepsilon, \qquad \delta p_i~=~ -\frac{\partial Q_H}{\partial q^i}\varepsilon, \qquad i~\in~\{1, \ldots, n\},\tag{3}$$
On the other hand, if we integrate out the momenta $p_i$, we get the corresponding Lagrangian action $$ S[q] ~= \int \! dt ~ L(q,\dot{q},t),\tag{4} $$ cf. this related Phys.SE post. The Hamiltonian eqs. $$0~\approx~\frac{\delta S_H}{\delta p_i} ~=~\dot{q}^i-\frac{\partial H}{\partial p_i} \tag{5}$$ for the momenta $p_i$ yield via the Legendre transformation the defining relation $$p_i~\approx~ \frac{\partial L}{\partial \dot{q}^i}\tag{6}$$ of Lagrangian momenta. Eqs. (5) & (6) establish a bijective correspondence between velocities and momenta.
If we take this bijective correspondence $\dot{q} \leftrightarrow p$ into account it is clear that Hamiltonian and Lagrangian conserved charges $$Q_H(q,p,t)~\approx~Q_L(q,\dot{q},t) \tag{7}$$ are in bijective correspondence. Below we will argue that the same is true for (vertical) infinitesimal quasi-symmetries on both sides.
On one hand, if we start with a (vertical) infinitesimal quasi-symmetry in (Hamiltonian) phase space $$ \varepsilon \frac{df^0_H}{dt}~=~\delta L_H ~=~\sum_{i=1}^n\frac{\delta S_H}{\delta p_i}\delta p_i + \sum_{i=1}^n\frac{\delta S_H}{\delta q^i}\delta q^i + \frac{d}{dt}\sum_{i=1}^n p_i~\delta q^i ,\tag{8}$$ it can with the help of eq. (5) be restricted to a (vertical) infinitesimal quasi-symmetry within the (Lagrangian) configuration space: $$ \varepsilon \frac{df^0_L}{dt}~=~\delta L ~=~ \sum_{i=1}^n\frac{\delta S}{\delta q^i}\delta q^i + \frac{d}{dt}\sum_{i=1}^n p_i~\delta q^i ,\tag{9}$$ In fact we may take $$f^0_L(q,\dot{q},t)~\approx~f^0_H(q,p,t) \tag{10}$$ the same. The restriction procedure also means that the bare Noether charges $$Q^0_H(q,p,t)~\approx~Q^0_L(q,\dot{q},t) \tag{11}$$ are the same, since there are no $\dot{p}_i$ appearance.
Conversely, if we start with an infinitesimal quasi-symmetry in (Lagrangian) configuration space, we can use Noether's theorem to generate a conserved quantity $Q_L$, and in this way close the circle.
Example: Consider $n$ harmonic oscillators with Lagrangian $$ L~=~\frac{1}{2}\sum_{k,\ell=1}^n \left(\dot{q}^k g_{k\ell}\dot{q}^{\ell} - q^k g_{k\ell} q^{\ell}\right),\tag{12}$$ where $g_{k\ell}$ is a metric, i.e. a non-degenerate real symmetric matrix. The Hamiltonian reads $$H~=~\frac{1}{2}\sum_{k,\ell=1}^n \left( p_k g^{k\ell} p_{\ell} + q^k g_{k\ell} q^{\ell}\right) ~=~\sum_{k,\ell=1}^n z^{k \ast} g_{k\ell} z^{\ell},\tag{13}$$ with complex coordinates $$ z^k~:=~\frac{1}{\sqrt{2}}(q^k+ip^k), \qquad p^k~:=~\sum_{\ell=1}^ng^{k\ell}p_{\ell}, \qquad \{z^{k \ast},z^{\ell}\}~=~ig^{k\ell}. \tag{14}$$ The Hamiltonian Lagrangian (2) reads $$ L_H~=~\sum_{k=1}^n p_k \dot{q}^k - H ~=~\frac{i}{2}\sum_{k,\ell=1}^n \left( z^{k \ast} g_{k\ell} \dot{z}^{\ell} - z^{k} g_{k\ell} \dot{z}^{\ell\ast} \right) - H, \tag{15}$$ Hamilton's eqs. are $$ \dot{z}^k~\approx~-iz^k, \qquad \dot{q}^k~\approx~p^k, \qquad \dot{p}^k~\approx~-q^k. \tag{16}$$ Some conserved charges are $$ Q_H ~=~ \sum_{k,\ell=1}^n z^{k \ast} H_{k\ell} z^{\ell} ~=~\sum_{k,\ell=1}^n \left( \frac{1}{2}q^k S_{k\ell} q^{\ell} +\frac{1}{2}p^k S_{k\ell} p^{\ell}+ p^k A_{k\ell} q^{\ell}\right), \tag{17}$$ where $$ H_{k\ell}~:=~S_{k\ell}+i A_{k\ell}~=~H_{\ell k}^{\ast} \tag{18}$$ is an Hermitian $n\times n$ matrix, which consists of a symmetric and an antisymmetric real matrix, $S_{k\ell}$ and $A_{k\ell}$, respectively. The conserved charges (17) generate an infinitesimal $u(n)$ quasi-symmetry of the Hamiltonian action $$\delta z_k~=~ \varepsilon\{z_k , Q_H\} ~=~-i \varepsilon\sum_{\ell=1}^n H_{k\ell} z^{\ell},$$ $$\delta q_k ~=~ \varepsilon\sum_{\ell=1}^n \left( A_{k\ell} q^{\ell} +S_{k\ell} p^{\ell} \right), \qquad \delta p_k ~=~ \varepsilon\sum_{\ell=1}^n \left( -S_{k\ell} q^{\ell} +A_{k\ell} p^{\ell} \right). \tag{19}$$ The bare Noether charges are $$ Q^0_H ~=~\sum_{k,\ell=1}^n p^k \left( A_{k\ell} q^{\ell} +S_{k\ell} p^{\ell} \right). \tag{20}$$ Also $$ f^0_H~=~\frac{1}{2}\sum_{k,\ell=1}^n \left( \frac{1}{2}p^k S_{k\ell} p^{\ell}- q^k S_{k\ell} q^{\ell}\right). \tag{21}$$ The corresponding infinitesimal $u(n)$ quasi-symmetry of the Lagrangian action (1) is $$\delta q_k ~=~ \varepsilon\sum_{\ell=1}^n \left( A_{k\ell} q^{\ell} +S_{k\ell} \dot{q}^{\ell} \right), \tag{22}$$ as one may easily verify.