The basic idea is the following one. For the sake of simplicity, I henceforth assume that every function does not depend explicitly on time (with a little effort, everything could be generalized dealing with a suitable fiber bundle over the axis of time whose fibers are spaces of phases at time $t$).
On a symplectic $2n$ dimensional manifold (a space of phases), $(M, \omega)$, where $\omega$ is the symplectic 2-form, you first define the Hamiltonian vector field $X_f$ associated to a smooth function $f: M \to \mathbb R$ as the unique vector field such that:
$$\omega(X_f, \cdot) = df\:.\tag{1}$$
The definition is well-posed because $\omega$ is non degenerate by hypotheses. $\omega$ is also antisymmetric and closed by hypotheses, therefore due to a theorem due to Darboux, on a suitable atlas which always exists $\omega = \sum_{i=1}^n dq^i \wedge dp_i$. In this picture you recover the standard $q-p$ formulation of Hamiltonian mechanics.
Next, you have the Poisson bracket of two smooth functions defined as
$$\{f, g\}:= \omega(X_f,X_g)\:.\tag{2}$$
The (generally local) one-parameter group of diffeomorphisms generated by $X_f$
turns out to be made of canonical transformations in the standard sense of Hamiltonian mechanics. $f$ is said to be the Hamiltonian generator of that transformation. Using Darboux' atlas, i.e. coordinates, $q^1,\ldots, q^n, p_1,\ldots, p_n$, both Hamilton equations and Poisson brackets assume the standard form more familiar to physicists.
If $H$ is a preferred function $f$ called the Hamiltonian function, the integral lines of $X_H$ are nothing but the solution of Hamilton equations.
With these definition it turns out that, if $[\:.,\:.]$ is the standard commutator of vector fields,
$$[X_f,X_g] = X_{\{f,g\}}\:.\tag{3}$$
As an immediate consequence of (3), you see that if $\{f,H\}=0$, then the integral lines of $X_H$ remains integral lines of $X_H$ also under the action of the group generated by $X_f$. In this case you have a dynamical symmetry.
Moreover, from (1) and (2), $$X_H(f) = \{f,H\}$$
so that $\{f,H\}=0$ also implies that $f$ is invariant under the Hamiltonian flow, i.e., it is a constant of motion.
The fact that $f$ is a constant of motion and that it generates (canonical) transformations which preserve the evolution of the system are equivalent facts.
This fantastic equivalence does not hold within the Lagrangian formulation of mechanics.
In this scenario, suppose that the $N$ dimensional Lie group $G$ freely acts on $M$ in terms of diffeomorphisms bijective. The one-parameters of the group define corresponding one parameter groups of diffeomorphisms whose generators have the same Lie algebra as that of $G$. So if $e_1,\ldots, e_n$ is a basis of $\mathbb g$ (the Lie algebra of $G$), with
$$[e_i,e_j] = \sum_{k=1}^N c^k_{ij}e_k$$
you correspondingly find, for the associated vector fields defining th corresponding one-parameter groups of diffeomorphisms
$$[X_i,X_j] = \sum_k c^k_{ij}X_k\:.$$
Suppose eventually that each $X_i$ can be written as $X_{f_i}$ for a corresponding smooth function $f_i : M \to \mathbb R$. In this case, the one-parameter group of diffeomorphisms generated by $X_f$ is a one-parameter group of canonical transformations. (This automatically happens when the action of $G$ preserves the symplectic form.)
Consequently,
$$X_{\{f_i,f_j\}} = [X_{f_i},X_{f_j}] = \sum_k c^k_{ij}X_{f_k}\:.$$
Using the fact that the Poisson brakes are bi-linear:
$$X_{\{f_i,f_j\} - \sum_k c^k_{ij}f_k} =0$$
and thus, since $f \mapsto X_f$ is injective up an additive constant to $f$,
$$\{f_i,f_j\} = q_{ij} +\sum_k c^k_{ij}f_k$$
the constants $q_{ij}$ generally appear, sometime (as it happens if $G=SO(3)$) you can re-absorb them in the definition of the $f_i$ which, in turn, are defined up to additive constants. (It is a co-homological problem depending on $G$).
I think you are confused about what a Lie algebra is:
A Lie algebra is a vector space $V$ together with a "bracket" $[-,-] : V\times V\to V$ that is linear, antisymmetric and obeys the Jacobi identity. Crucially, nothing in the definition of a Lie algebra says that the elements of $V$ are anything more than vectors, so in the abstract setting it does not make sense to talk about them "commuting" since a vector space carries no native notion of multiplication.
Now, the vast majority of examples of Lie algebras comes from algebras of operators, i.e. linear maps on some vector space. For such operators, you have a natural notion of multiplication (simply carrying the transformations they representation out in succession), and you can talk about the commutator $AB-BA$. If we now take the commutator as a bracket on the space of operators, that space becomes a Lie algebra. But, crucially, nothing forces us to take the commutator as the bracket, in particular, we can have the following:
In classical mechanics we have the algebra of classical observables as smooth $\mathbb{R}$-valued functions $C^\infty(M)$ on phase space $M$. Such functions can naturally be multiplied with each other and therefore also have a notion of "commutator", but it's just always zero since $\mathbb{R}$ is commutative unlike rings of operators. But, nevertheless, we may define a bracket on $C^\infty(M)$ by
$$ \{f,g\} = \frac{\partial f}{\partial x}\frac{\partial g}{\partial p} - \frac{\partial f}{\partial p}\frac{\partial g}{\partial x},$$
the Poisson bracket. This is non-zero even though the functions $f,g$ commute under multiplication, and therefore gives a non-trivial Lie algebra structure on $C^\infty(M)$. That they commute under naive multiplication has nothing to do with their Poisson bracket. Note that functions with $\{f,g\} = 0$ are sometimes said to "Poisson commute", which means they commute under the in general non-commutative "multiplication" $f\bullet g := \frac{\partial f}{\partial x}\frac{\partial g}{\partial p}$.
The significance of the Lie/Poisson bracket is that given two observables $f,g$ it tells you how one changes under the other infinitesimally. For example: the Hamiltonian is the generator of time translation, so $\partial_t f(t) = \{H,f\}$ (up to a sign). Angular momentum $L = x\times p$ is the generator of rotation, so if $\phi$ is the variable angle of rotation (say, around the z-axis), then $\partial_\phi (R_z(\phi) f) = \{L_z,f\}$, where $R_z(\phi)$ is the operator that acts by rotation on the function $f$, and so on.
Best Answer
The classical poisson bracket with the generator of any transformation gives the infinitesimal evolution with respect to that transformation. The familiar
$$ \partial_t f = \{H,f\}$$
means nothing else than the time evolution of any observable is given by its Poisson bracket with the Hamiltonian, which is the generator of time translation. More generally, given any element $g$ of the Lie algebra of observables on the phase space, the infinitesimal evolution under the transformation that it generates (parametrized by an abstract "angle" $\phi$) is given by
$$ \partial_\phi f = \{g,f\}$$
What is meant by this is that every observable $f$ gives rise (by Lie integration) to a symplectomorphism $\mathrm{exp}(\phi f)$ on the phase space (since the true Lie integration of observables projects down surjectively onto the symplectomorphisms). More precisely, the statement above therefore reads
$$ \partial_\phi( f \circ \mathrm{exp}(\phi g))\rvert_{\phi = 0} = \{g,f\}$$
so that vanishing Poisson bracket implies $f \circ \mathrm{exp}(\phi g) = f$, i.e. invariance of the observable under the induced symplectomorphism.
Thus, if the Poisson bracket of $f$ and $g$ vanishes, that means that they describe an infinitesimal transformation that is a symmetry for the other.
For example, an observable is invariant under rotation if its Poisson bracket with all $L^i = \epsilon^{ijk}x^jp^k$ (components of $\vec L = \vec x \times \vec p$) vanishes.
For $x$ and $p$, the non-vanishing $\{x,p\}$ means the rather trivial insight that $x$ is not invariant under the translations generated by the momentum.
Fun fact: Wondering what the actual Lie integration of these infinitesimal symmetries might be leads directly to the quantomorphism group, and is a natural starting point for geometric quantization, as discussed in this answer.
Responding to the tangential question in a comment:
No, it means that the "Lagrangian" (you cannot really take the Lagrangian, because it is not a function on the phase space) is invariant under varying the momentum of the system (since $x$ generates "translations" in momentum). The Hamiltonian equivalent of Noether's theorem is simply that $f$ is conserved if and only if
$$ \{H,f\} = 0$$
since conservation means invariance under time evolution.