I understand the mathematics of commutation relations and anti-commutation relations, but what does it physically mean for an observable (self-adjoint operator) to commute with another observable (self-adjoint operator) in quantum mechanics? 

E.g. an operator $A$ with the Hamiltonian $H$?

Let us first restate the mathematical statement that two operators $\hat A$ and $\hat B$ commute with each other. It means that
$$\hat A \hat B - \hat B \hat A = 0,$$
which you can rearrange to 
$$\hat A \hat B = \hat B \hat A.$$

If you recall that operators act on quantum mechanical states and give you a new state in return, then this means that with $\hat A$ and $\hat B$ commuting, the state you obtain from letting first $\hat A$ and then $\hat B$ act on some initial state is the same as if you let first $\hat B$ and then $\hat A$ act on that state:
$$\hat A \hat B | \psi \rangle = \hat B \hat A | \psi \rangle.$$

This is not a trivial statement. Many operations, such as rotations around different axes, do not commute and hence the end-result depends on how you have ordered the operations.

So, what are the important implications? Recall that when you perform a quantum mechanical measurement, you will always measure an eigenvalue of your operator, and after the measurement your state is left in the corresponding eigenstate. The eigenstates to the operator are precisely those states for which there is no uncertainty in the measurement: You will always measure the eigenvalue, with probability $1$.
An example are the energy-eigenstates. If you are in a state $|n\rangle$ with eigenenergy $E_n$, you know that $H|n\rangle = E_n |n \rangle$ and you will always measure this energy $E_n$.

Now what if we want to measure two different observables, $\hat A$ and $\hat B$? If we first measure $\hat A$, we know that the system is left in an eigenstate of $\hat A$. This might alter the measurement outcome of $\hat B$, so, in general, the order of your measurements is important. Not so with commuting variables! It is shown in every textbook that if $\hat A$ and $\hat B$ commute, then you can come up with a set of basis states $| a_n b_n\rangle$ that are eigenstates of both $\hat A$ and $\hat B$. If that is the case, then any state can be written as a linear combination of the form
$$| \Psi \rangle = \sum_n \alpha_n | a_n b_n \rangle$$
where $|a_n b_n\rangle$ has $\hat A$-eigenvalue $a_n$ and $\hat B$-eigenvalue $b_n$.
Now if you measure $\hat A$, you will get result $a_n$ with probability $|\alpha_n|^2$ (assuming no degeneracy; if eigenvalues are degenerate, the argument still remains true but just gets a bit cumbersome to write down). What if we measure $\hat B$ first? Then we get result $b_n$ with probability $|\alpha_n|^2$ and the system is left in the corresponding eigenstate $|a_n b_n \rangle$. If we now measure $\hat A$, we will always get result $a_n$. The overall probability of getting result $a_n$, therefore, is again $|\alpha_n|^2$. So it didn't matter that we measure $\hat B$ before, it did not change the outcome of the measurement for $\hat A$. 

EDIT Now let me expand even a bit more. So far, we have talked about some operators $\hat A$ and $\hat B$. We now ask: What does it mean when some observable $\hat A$ commutes with the Hamiltonian $H$? First, we get all the result from above: There is a simultaneous eigenbasis of the energy-eigenstates and the eigenstates of $\hat A$. This can yield a tremendous simplification of the task of diagonalizing $H$. For example, the Hamiltonian of the hydrogen atom commutes with $\hat L$, the angular momentum operator, and with $\hat L_z$, its $z$-component. This tells you that you can classify the eigenstates by an angular- and magnetic quantum number $l$ and $m$, and you can diagonalize $H$ for each set of $l$ and $m$ independently. There are more examples of this.

Another consequence is that of time dependence. If your observable $\hat A$ has no explicit time dependency introduced in its definition, then if $\hat A$ commutes with $\hat H$, you immediately know that $\hat A$ is a constant of motion. This is due to the Ehrenfest Theorem
$$\frac{d}{dt} \langle \hat A \rangle = \frac{-i}{\hbar} \langle [\hat A, \hat H] \rangle 
+ \underbrace{\left\langle \frac{\partial \hat A}{\partial t} \right\rangle}_{=\;0\,\text{by assumption}}$$
