Measurement in quantum mechanics consists of two rules. The first one - called the Born rule - determines the possible measurement outcomes and their probabilities and the second determines the post-measurement state associated with each outcome. Consequently, there are different ways to define equivalence between measurements. In a weaker form, one declares two measurements equivalent if they have the same outcome probability distribution. In a stronger form, one in addition demands that for each outcome the associated post-measurement states are the same.
The authors of the paper have the weaker form of equivalence in mind as can be seen easily by considering a qubit and setting $M=Z$ (the so-called computational basis measurement) and $U=H$ (the Hadamard gate). Measurement of $M$ leaves the qubit either in $|0\rangle$ or in $|1\rangle$ state. Whereas measurement of $UMU^\dagger = HZH = X$ leaves the qubit either in $|+\rangle$ or in $|-\rangle$ state.
Let us derive the weak equivalence in the case of projective measurement. This type of measurement is associated with a Hermitian operator
$$
M = \sum_{m} \lambda_m P_m
$$
where $m$ ranges over eigenvalues $\lambda_m$ of $M$ which are the possible measurement outcomes and $P_m$ is the projector on the eigenspace of $M$ associated with eigenvalue $\lambda_m$.
Probability $p(m|M,\psi)$ of obtaining outcome $\lambda_m$ when measuring $M$ on state $|\psi\rangle$ is by the Born rule
$$
p(m|M,\psi) = \langle\psi|P_m|\psi\rangle.
$$
In order to verify the claim that application of $U$ followed by measurement of $M'=UMU^\dagger$ is equivalent - in the weaker sense - to measurement of $M$ on the original state we need to check that both yield the same outcomes $\lambda_m$ and that the probabilities associated with each outcome are the same.
First, note that $M$ and $UMU^\dagger$ are similar so they have the same eigenvalues and so the set of possible outcomes of these two measurements are the same.
Second, suppose we begin in state $|\psi\rangle$, apply $U$ to get $|\psi'\rangle = U|\psi\rangle$ and measure $M'=UMU^\dagger$. Note that
$$
M' = UMU^\dagger = U \left(\sum_{m} \lambda_m P_m\right)U^\dagger = \sum_{m} \lambda_m UP_mU^\dagger = \sum_{m} \lambda_m P_m'
$$
where we defined $P_m' = UP_mU^\dagger$. The probability of measuring $\lambda_m$ is
$$
p(m|M', \psi') = \langle\psi'|P_m'|\psi'\rangle = \langle\psi|U^\dagger UP_mU^\dagger U|\psi\rangle = \langle\psi|P_m|\psi \rangle = p(m|M, \psi).
$$
Therefore the two measurements are equivalent in the weaker sense.
Now, let us see that they are not equivalent in the stronger sense. Post-measurement state when outcome $\lambda_m$ was obtained when measuring $M$ on the state $|\psi\rangle$ is
$$
|\psi_{m,M}\rangle = \frac{P_m|\psi\rangle}{\sqrt{p(m)}}.
$$
Suppose now that we begin in state $|\psi\rangle$, apply $U$ to get $|\psi'\rangle = U|\psi\rangle$ and measure $M'=UMU^\dagger$ obtaining $\lambda_m$. This time the post-measurement state is
$$
|\psi_{m,M'}'\rangle = \frac{P_m'|\psi'\rangle}{\sqrt{p(m)}} = \frac{UP_mU^\dagger U|\psi\rangle}{\sqrt{p(m)}} = U|\psi_{m,M}\rangle.
$$
Clearly this is not in general the same state as $|\psi_{m,M}\rangle$.
Note that strong version of equivalence is in fact operator equality. This justifies the omission of the adjective "weak".