First of all, the "conservation of information" is called the Liouville's theorem and it is a very desirable property of nature. It translates to: the volume of any region of the phase space remains constant under time evolution. Put in other words, the trajectories in phase space never join or fork. It is basically equivalent to determinism.
The "conservation of information" means that there's always only one past and only one future.
The Liouville's theorem does hold in Newtonian physics. It is also needed for thermodynamics. Without it, thermodynamics doesn't work.
Now we can break the Liouville's theorem in 3 ways, by introducing the following two phenomena or both:
1. The information is created from nowhere; the phase space trajectories fork; there is one past but many possible futures; the world is not deterministic.
2. The information is lost; the phase space trajectories join; there is only one future but many possible pasts (that means our memories are unreliable); the world is future-deterministic but nondeterministic when played backwards.
3. Both of the above.
Now notice that general relativity breaks the Liouville's theorem the second way while quantum mechanics the first way.
In QM one and same wave function may collapse into several different states, governed only by probability (and not by some hidden determinism, which is already excluded by the current state of knowledge). Information is created out of nowhere.
In GR several different objects may collapse into the same black hole, provided only their mass is equal. All other information is lost, since GR alone does not allow anything to flee from the black hole.
All that means, not GR nor QM are time-symmetric (without resorting to negative mass in GR case).
Now we have quantum gravity. (Hawking radiation falls into quantum gravity already.) The naive approach to quantum gravity may mean that the Liouville's theorem is broken in both ways, so that the information isn't conserved at all and may be annihilated and created at random.
In the second attempt, we might try to devise a theory where both effects somehow cancel.
Many such theories have been created and all of them are counter-intuitive :).
One of them says that information may be recovered from black hole using the wavefunction as carrier. The process is:
1. A particle (say electron) falls into black hole.
2. An entangled virtual electron-positon pair appears outside the event horizon.
3. The virtual positon falls into the black hole.
4. The initial electron and the virtual positon collide.
5. The positon and the outside virtual electron were entangled, so the inside electron gets entangled with the outside electron.
6. The outside electron gets real by the process and also inherits all the inside electron's information thanks to entanglement.
7. The colliding pair inside the black hole becomes virtual and annihilates, producing virtual collision remnants that disappear without trace.
8. The outside electron escapes the black hole as the Hawking radiation, carrying all the initial electron's information.
This way, the information can escape the black hole thus is always conserved.
Here is what I am not sure, if it's the process annihilating that leads to information loss, does it has to be inside a black hole?
The supposed information loss does not happen in any point of space. It is a general property of the setup.
If you throw some object into a black hole, the information about it is lost as soon as the fall into the hole is inevitable (provided that black holes really destroy information).
You may say in a sense that the information is lost when the object passes the event horizon. But the exact position of the event horizon is not well defined, so it doesn't make much sense.
The information is lost when you loose any chance to fetch the information back from the destroyed object and that might be well before the fall into the event horizon.
If I have an anti-particle, and let it annihilating with a normal particle, doesn't this produce the same "information loss" result?
No, you can restore the information from the annihilation remnants.