What is the physical meaning of commutators in quantum mechanics?
Self adjoint operators enter QM, described in complex Hilbert spaces, through two logically distinct ways. This leads to a corresponding pair of meanings of the commutator.
The former way is in common with the two other possible Hilbert space formulations (real and quaternionic one): Self-adjoint operators describe observables.
Two observables can be compatible or incompatible, in the sense that they can or cannot be measured simultaneously (corresponding measurements disturb each other when looking at the outcomes). Up to some mathematical technicalities, the commutator is a measure of incompatibility, in view of the generalizations of Heisenberg principle you mention in your question. Roughly speaking, the more the commutator is different form $0$, the more the observables are mutually incompatible. (Think of inequalities like $\Delta A_\psi \Delta B_\psi \geq \frac{1}{2} |\langle \psi | [A,B] \psi\rangle|$. It prevents the existence of a common eigenvector $\psi$ of $A$ and $B$ - the observables are simultaneously defined - since such an eigenvector would verify $\Delta A_\psi =\Delta B_\psi =0$.)
The other way self-adjoint operators enter the formalism of QM (here real and quaternionic versions differ from the complex case) regards the mathematical description of continuous symmetries. In fact, they appear to be generators of unitary groups representing (strongly continuous) physical transformations of the physical system. Such a continuous transformation is represented by a unitary one-parameter group $\mathbb R \ni a \mapsto U_a$. A celebrated theorem by Stone indeed establishes that $U_a = e^{iaA}$ for a unique self-adjoint operator $A$ and all reals $a$. This approach to describe continuous transformations leads to the quantum version of Noether theorem just in view of the (distinct!) fact that $A$ also is an observable.
The action of a symmetry group $U_a$ on an observable $B$ is made explicit by the well-known formula in Heisenberg picture:
$$B_a := U^\dagger_a B U_a$$
For instance, if $U_a$ describes rotations of the angle $a$ around the $z$ axis, $B_a$ is the analog of the observable $B$ measured with physical instruments rotated of $a$ around $z$.
The commutator here is a first-order evaluation of the action of the transformation on the observable $B$, since (again up to mathematical subtleties especially regarding domains):
$$B_a = B -ia [A,B] +O(a^2) \:.$$
Usually, information encompassed in commutation relations is very deep. When dealing with Lie groups of symmetries, it permits to reconstruct the whole representation (there is a wonderful theory by Nelson on this fundamental topic) under some quite mild mathematical hypotheses. Therefore commutators play a crucial role in the analysis of symmetries.
I'd like to expand a little bit on the interpretation of commutators as a measure of disturbance (related to incompatibility, as touched on in the other answers). My interpretation of the commutator is that $[A,B]$ quantifies the extent to which the action of $B$ changes the value of the dynamical variable $A$, and vice versa.
Let's assume that $A$ is a self-adjoint operator with a discrete non-degenerate spectrum of eigenvalues $\{a\}$ with associated eigenkets $\lvert a\rangle$. Then you can show that, for any operator $B$, the following decomposition exists $$ B = \sum_{\Delta} B(\Delta),$$ such that $$[A,B(\Delta)] = \Delta B(\Delta),$$ where $B(\Delta)$ is defined below. Viewing the commutator $[A,.]$ as a linear operator, this has the form of an eigenvalue equation. The eigenvalues $\Delta$ are given by differences between pairs of eigenvalues of $A$, e.g. $\Delta = a'-a$. The specific form of the eigenoperators $B(\Delta)$ is $$ B(\Delta) = \sum_{a} \langle a+\Delta\rvert B\lvert a\rangle \;\lvert a+\Delta\rangle\langle a\rvert.$$ This demonstrates that the $B(\Delta)$ are "ladder operators" which act to increase the value of the variable $A$ by an amount $\Delta$. The commutator thus induces a natural decomposition of $B$ into contributions that change the value of $A$ by a given amount. A simple example is the well known commutation relation between spin$-1/2$ operators: $$[\sigma^z,\sigma^x] = \mathrm{i}2\sigma^y = +2\sigma^+ - 2\sigma^-.$$ This tells you that $\sigma^x$ has two parts, which either increase or decrease the spin projection onto the $z$ axis by two "units", which in this case means $\pm 2\times\frac{\hbar}{2} = \pm \hbar$.
In general, the full commutator is $$ [A,B] = \sum_{\Delta} \Delta B(\Delta). $$ The $B(\Delta)$ are linearly independent$^{\ast}$, therefore the commutator vanishes only if $B(\Delta) = 0$ for all $\Delta \neq 0$, i.e. if $B$ does not change the value of $A$. If $[A,B]\neq 0$, one can get a measure of how much $B$ changes $A$ by computing the Hilbert-Schmidt norm (squared) of the commutator: $$\mathrm{Tr}\left\{[A,B]^{\dagger}[A,B]\right\} = \sum_{a,a'}(a-a')^2\lvert\langle a\rvert B \lvert a' \rangle\rvert^2. $$ This is the sum of the (squared) matrix elements of $B$ which link different eigenstates of $A$, weighted by the corresponding change in eigenvalues (squared). So this clearly quantifies the change in $A$ brought about by applying $B$.
Now the not-so-obvious part: what does "changing $A$ by applying $B$" mean physically? As noted by Valter, evolution and transformations in QM are carried out formally by applying unitary operators generated by observables, not by applying the observables themselves. This relates to the above decomposition in the following way. Suppose that we take $A$ to be the Hamiltonian $H$. Then it is straightforward to show that the evolution of $B$ in the Heisenberg picture is given by $$B(t) = e^{i H t} B e^{-i H t} = \sum_{\Delta} e^{i\Delta t} B(\Delta), $$ where here $\Delta$ are the Bohr frequencies of the system under consideration. The jump operators $B(\Delta)$ can be interpreted as the Fourier components of the operator-valued function $B(t)$. In the context of perturbation theory, we often approximate the effect of unitary evolution by the application of a Hermitian operator (the perturbing Hamiltonian), in which case the interpretation of the jump operators is clear: they describe the transitions between energy eigenstates caused by the perturbation $B$. The oscillating time dependence ultimately leads to energy conservation as a frequency-matching condition.
This is hardly a complete answer to the rather optimistic question of "what do commutators mean physically". However it might provide some food for thought for the curious student.
$^{\ast}$This follows since the $B(\Delta)$ are orthogonal with respect to the Hilbert-Schmidt inner product: $$ \mathrm{Tr}\left\{ B(\Delta)^{\dagger} B(\Delta') \right\} = \delta_{\Delta,\Delta'} \sum_a \lvert \langle a \rvert B \lvert a+\Delta \rangle \rvert^2,$$ where the Kronecker delta symbol $\delta_{\Delta,\Delta'}$ equals 1 if $\Delta = \Delta'$, and 0 otherwise.
At a basic level :
1) if $[A,B]=0$, and if $A$ and $B$ are infinitesimal generators of a symmetry (so also conserved quantities), this means that both $A$ is invariant by $B$, and $B$ is invariant by $A$.
For instance, $[H,J_z]=0$, means that the angular momentum is conserved during time evolution, and that the hamiltonian is invariant by rotation.
As @Valter Moretti says, a non-null commutator $[A,B]$ measures the deviation from (both) symmetries.
2) Commutators of type $[A, B] = \pm B$, if $A$ is associated to a discrete spectrum, means that $B$ is a raising/lowering operator, with a " $A$-charge" $\pm 1$.
An obvious example is $[J_z, J_\pm]= \pm J_\pm$
3) Commutation relations of type $[\hat A, \hat B]= i \lambda$, if $ \hat A$ and $\hat B$ are observables, corresponding to classical quantities $a$ and $b$, could be interpreted by considering the quantities $I = \int a \,db$ or $J = \int b \,da$. These classical quantities cannot be traduced in quantum observables, because the uncertainty on these quantities is always around $\lambda$.
For instance, $[\hat x,\hat p] = i \hbar$ shows that there is no quantum observable corresponding to the action $S =\int (\vec p\,d \vec x - E\, dt)$.