Consider canonical transformations $\Phi_\lambda:p_i,q^j \to p'_i,q'^j$ depending smoothly on a parameter $\lambda$ such that $\lambda=0$ reduces to an identity. Such a transformation is at least locally expressible (for $\lambda \approx 0$) as
$$\Phi_\lambda(z) = \exp(\lambda \{z,G\})$$
where $G$ is some generating function and $z=(p_i,q^j)$. To linear order in $\lambda$ you can express this relation as
$$p'_i = p_i + \lambda \{p_i,G\}+\mathcal{O}(\lambda^2) = p_i - \lambda \frac{\partial G}{\partial q^i}+\mathcal{O}(\lambda^2)$$
$$q'^j = q^j + \lambda \{q^j,G\}+\mathcal{O}(\lambda^2) = q^j + \lambda \frac{\partial G}{\partial p_j}+\mathcal{O}(\lambda^2)$$
You can also view $G$ as a sort of "Hamiltonian" and $q'^j(\lambda),p'_i(\lambda)$ as the trajectories corresponding to its Hamilton's equations.
Now one can ask what sort of infinitesimal transform of this type leaves the Hamiltonian invariant. It is easy to show that under this transform the Hamiltonian gets push-forwarded as
$$H'(p_i,q^j)\equiv H\left(p'_k(p_i,q^j),q'^l(p_i,q^j)\right) = H(p_i,q^j) + \lambda \{H,G\} + \mathcal{O}(\lambda^2)$$
(I would recommend to verify the last equation to understand what is happening here.)
In other words, when a function is a generator of an infinitesimal symmetry of the phase space, it is also an integral of motion and vice versa. (Do note that there are also discrete symmetries which cannot be characterized in this way.)
One last note: a phase-space symmetry is not quite the same thing as a spatial symmetry (a symmetry on the $q^j$ space). However, it is easy to show that when a physical problem has a spatial configuration symmetry characterized by an infinitesimal transform $q'^j = q^j + \epsilon V^j(q^j)$, then this is lifted to a phase-space symmetry by using the generating function $G = \sum_j V^jp_j$.