I'll answer the first question; these might be better served as two distinct questions.
Let's start with the mathematical definition quoted in the paper: for a quantum channel $\Phi(\rho)$ acting on density operators and a set of unitary operators $U$ belonging to some group, the equality
$$\Phi(U \rho U^\dagger)=U \Phi(\rho)U^\dagger$$ implies that the channel is covariant with respect to the group. For a simple unitary channel like $\Phi(\rho)=V\rho V^\dagger$, the covariance property is equivalent to finding a group of unitaries that commute with $V$ ($UV-VU=0$ for all $U$ in the group).
Now, for words: the action of first evolving the state according to the unitary and second according to the channel is the same as the action of first evolving the state according to the channel and second according to the unitary. In other words, the order in which the channel and the unitaries are applied is irrelevant for all unitaries in this particular group. In some sense, the channel and the unitaries act on different parts of the state, so that they each leave each other's part untouched. Different channels can be covariant with respect to different groups, so the covariance properties of a channel tell us something about what parts of the state the channel does and does not affect. These "parts of the state" may correspond to different physical properties, so we might be pleased to learn that a channel is covariant with respect to a particular group. For example, if you know that your channel is covariant with respect to the group of rotations, then turning your state before or after applying the channel yields the same result (which would make sense if your channel didn't care about the orientation of your state).
Easy examples are quantum channels that only operate on a block-diagonal portion of the density matrix: then, the set of unitaries acting on the rest of the density matrix will always commute with the action of the channel. This group of unitaries tells us that the channel has in some sense only acted trivially on one block of the density matrix. I say trivially because we can think of more sophisticated examples, such as channels that always replace a block of the density matrix with an identity matrix, where the same set of unitaries will commute with the action of the channel but the channel's action on the relevant block was not negligible.