There're different levels of making this statement precise. Here's one:

Physics is a deterministic theory, even at a quantum level where we call determinism unitarity. (Leaving the measurement problem & collapse of the wave function aside for a moment.)

Determinism means, we can start with one state of a given physical system and basically hit the "fast forward" or "backward" button to see what the state was like in the past and what other state it's going to evolve to in the future. This assignment of future states to past or current states and vice versa is unique and one-to-one, hence deterministic:

past -> future

A --------> X

B --------> Y

where the arrows indicate evolution in time.

This is what allows us to make predictions for the future outcome of experiments or draw conclusions from experimental results in the first place.

Now, the problem with black holes and in particular their evaporation through Hawking radiation is that Hawking radiation does not in any known way depend on what once fell into the black hole but, instead, just on the black hole's total mass. So let's say you start with two different mass distributions A, B of the same mass M and each collapses and forms a black hole BH of mass M. You could argue that the original matter is still somewhere inside the black hole, so the black hole's internal state still depends on the past matter distribution and we should indicate this by talking about black hole BH_A and black hole BH_B. So we have:

A -> BH_A

B -> BH_B

Then Hawking radiation sets in and both black holes vanish eventually and give way to a state of Hawking radition H:

A -> BH_A -> H

B -> BH_B -> H

As mentioned before, the Hawking state H really only depends on the mass M of the black hole, so since both BH_A and BH_B had the same mass, we will also get the same final Hawking state H. As you can see, the mapping {past events -> future events} is no longer one-to-one: From H alone you cannot draw any conclusions about the original state anymore. (Was it A or B?)

This is (one half of) what is meant when people say that information is lost (about the original state).

The other half is that a classical (eternal) black hole state is a so-called pure state from the point of quantum mechanics: There is never any doubt about its precise state. It is always perfectly described by only its mass (and angular momentum and charge)[1]. Hawking radiation, however, is not such a state once the black hole has fully evaporated. Instead, at that point it is a so-called mixed quantum state meaning that it could be any of a whole "mix" of states. We can only give a probability distribution for what the state is in reality; in Hawking's case it's a perfectly thermal distribution. (Side remark: I should point out that such a mixed state is not the same thing as a superposition in quantum mechanics! In particular, the probability distribution here is not related to any wave function.)

Anyway, what this means is that we have now evolved from a black hole state BH, that was precisely known, to another state about which nothing can be said anymore outside of the probability distribution:

BH -> Hawking_1 or Hawking_2 or Hawking_3 or …?

This constitutes a loss of predictability.

TL;DR To sum up, there are two aspects: The loss of information and the loss of predictability. Both are just the two sides of the same medal: The breakdown of determinism.

[1] https://en.wikipedia.org/wiki/No-hair_theorem