Fragment "with no loss of meaning" is essentially the same as "without loss of meaning". One can employ such a substitution if that's easier for one to comprehend.
In the phrase "can be omitted with no loss" the preposition "with" establishes the causal relationship between the verb "omitted" and the noun phrase "no loss". Thus the overall explanation of
... the word “that” often can be omitted with no loss of meaning.
is that the omission (of the word "that") often causes no loss of meaning, i.e. the meaning often stays the same even if the word "that" is omitted.