Where does deleted information go? I've heard that, in classical and quantum mechanics, the law of conservation of information holds. 
I always wonder where my deleted files and folders have gone on my computer. It must be somewhere I think. Can anyone in principle recover it even if I have overwritten my hard drive?
 A: Short Answer
The information is contained in the heat given off by erasing the information. Landauer' Principle states that erasing information in a computation, being a thermodynamically irreversible process, must give off heat proportional to the amount of information erased in order to satisfy the second law of thermodynamics.  The emitted information is hopelessly scrambled though and recovering the original information is impossible in practice. Scrambling of information is what increasing entropy really means in plain English. Charles H. Bennett and Rolf Landauer developed the theory of thermodynamics of computation. The main results are presented in The thermodynamics of computation—a review.
Background
Erasure of information and the associated irreversibility are macroscopic/thermodynamic phenomena. At the microscopic level everything is reversible and all information is always preserved, at least according to the currently accepted physical theories, though this has been questioned by notable people such as Penrose and I think also by Prigogine.  Reversibility of basic physical laws follows from Liouville's_theorem for classical mechanics and unitarity of the time evolution operator for quantum mechanics. Reversibility implies the conservation of information since time reversal can then reconstruct any seemingly lost information in a reversible system.
The apparent conflict between macroscopic irreversibility and microscopic reversibilty is known as Loschmidt's paradox, though it is not actually a paradox.
In my understanding sensitivity to initial conditions, the butterfly effect, reconciles macroscopic irreversibility with microscopic reversibility. Suppose time reverses while you are scrambling an egg. The egg should then just unscramble like in a film running backwards. However, the slightest perturbation, say by hitting a single molecule with a photon, will start a chain reaction as that molecule will collide with different molecules than it otherwise would have. Those will in turn have different interactions then they otherwise would have and so on. The trajectory of the perturbed system will diverge exponentially from the original time reversed trajectory. At the macroscopic level the unscrambing will initially continue, but a region of rescrambling will start to grow from where the photon struck and swallow the whole system leaving a completely scrambled egg.
This shows that time reversed states of non-equilibrium systems are statistically very special, their trajectories are extremely unstable and impossible to prepare in practice. The slightest perturbation of a time reversed non-equilibrium system causes the second law of thermodynamics to kick back in.
The above thought experiment also illustrates the Boltzmann brain paradox in that it makes it seem that a partially scrambled egg is more likely to arise form the spontaneous unscrambling of a completely scrambled egg than by breaking an intact one, since if trajectories leading to an intact egg in the future are extremely unstable, then by reversibility, so must trajectories originating from one in the past. Therefore the vast majority of possible past histories leading to a partially scrambled state must do so via spontaneous unscrambling. This problem is not yet satisfactorily resolved, particularly its cosmological implications, as can be seen by searching Arxiv and Google Scholar.
Nothing in this depends on any non classical effects.
A: The deletion of data only allows other data to be saved where that data was previously saved. In other words, deletion is not what it seems, it is just freeing up the space that was otherwise occupied. If you save something on top of this space(overwrite it), then it is more difficult to recover via HD recovery tools. So yes it is possible to recover if overwritten but the probability of recovering the data decreases as the space is continually overwritten. 
A: To add to Daniel Maher's Excellent Answer and, referring to the same reference, Charles Bennett, "The Thermodynamics of Computation: A Review", Int. J. Theo. Phys., 21, No. 12, 1982.
A simple summary to Daniel's answer and also to your question "where has the information gone?" is - after deletion, it is now encoded in the *physical states of the matter (quantum states of "stuff") that makes up the computer and also its environment. As Daniel says, physics at a microscopic level is reversible, so you can imagine the deletion process as a "movie" (albeit one with a stupendously complicated plot) where the changes of state in the deleted memory chips influences the matter around the system so that the latter changes state subtly. Nature does not forget it got into its state at any time - or, more formally, the state of the World is a one to one (bijective) function of its state at any other time. So, you can, in principle, now run your movie backwards and see the configurations of the matter around the memory chips restore their former values.
In the paper that Daniel and I cite, Bennett invents perfectly reversible mechanical gates ("billiard ball computers") whose state can be polled without the expenditure of energy and then used such mechanical gates to thought-experimentally study the Szilard Engine and to show that Landauer's Limit arises not from the cost of finding out a system's state (as Szilard had originally assumed) but from the need to continually "forget" former states of the engine.
Probing this idea more carefully, as also done in Bennett's paper: One can indeed conceive non-biological simple finite state machines to realise the Maxwell Daemon - this has been done in the laboratory! see at the end - and as the Daemon converts heat to work, it must record a sequence of bits describing which side of the Daemon's door (or engine's piston, for an equivalent discussion of the Szilard engine) molecules were on. For a finite memory machine, one needs eventually to erase the memory so that the machine can keep working. However, "information" ultimately is not abstract - it needs to be "written in some kind of ink" you might say - and that ink is the states of physical systems. The fundamental laws of physics are reversible, so that one can in principle compute any former state of a system from the full knowledge of any future state - nothing gets lost. So, if the finite state machine's memory is erased, the information encoded that memory must show up, recorded somehow, as changes in the states of the physical system making up and surrounding the physical memory. So now those physical states behave like a memory: eventually those physical states can encode no more information, and the increased thermodynamic entropy of that physical system must be thrown out of the system, with the work expenditure required by the Second Law, before the Daemon can keep working. The need for this work is begotten of the need to erase information, and is the ultimate justification for Landauer's principle.
Going back to your computer: you can even do some back of the envelope calculations as to what would happen if you could reversibly store every step of a calculation in a bid to get around the Landauer Limit, see Emilio Pisanty's bounding of the information content of the human brain. You end up with your head blasting off in a scene that evokes a Dr Who regeneration (after Christopher Eccelston) with ion beams streaming from the neck! Also note, however, that even reversible computers need to erase information to initialise their states at the beginning of any computation. The uninitialised states need to be encoded in the states of physical systems too during the power up process.
Beyond heads blowing off from stupendously thermalised matter, there is also the Berkenstein Bound  from the field of Black Hole Thermodynamics is  (see the Wiki page with this name), which is the maximum amount information that can be encoded in a region of space with radius $R$ containing mass-energy $E$, it is:
$$I\leq \frac{2\,\pi\,R\,E}{\hbar\,c\,\log 2}$$
where $I$ is the number of bits contained in quantum states of that region of space. This bound was derived by doing a thought experiment wherein Berkenstein imagined lowering objects into black holes see this question and then deduced the above bound by assuming that the second law of thermodynamics holds. It works out to about $10^{42}$ bits to specify the full quantum state of an average sized human brain. This is to be compared to estimates of the Earth's total computer storage capacity, which is variously reckonned to be of the order of $10^{23}$ bits (see the Wikipedia "Zettabyte" page, for instance) as of writing (2013).
So, ultimately, a computer erasing its memory throughout computations and sundered from the rest of the Universe would fill up all the information encoding capacity of any finite region in space.
You might also like to browse a couple of articles I wrote on my website 
Information is Physical: Landauer’s Principle and Information Soaking Capacity of Physical Systems
and
Free Energies: What Does a Physical Chemist Mean when He/She Talks of Needing Work to Throw Excess Entropy Out of a Reaction?
A: I would like to start by stating that there are at least 3 definitions of "delete" (computer or hard drive) information.  The first is done by "quick delete." This process changes the "index" that has the location of the data and marks the associated storage space as "available," but the data itself is unaffected, so it can be easily "recovered" as long as it is not overwritten. If new information is written, then the old information is lost.
The second method is the "format delete."  This process overwrites all of the sectors and all of the tracks with the same "character" (the letter A, for example), thus destroying the previous information.  
The third method, which I consider the "real delete," is done by means of an AC electromagnet.  This method 
"scrambles" the ferromagnetic molecules on the surface of the disk, destroying any previous orientation the molecules had, thereby truly destroying any meaning (or information) they had. 
I feel that the third method is the real delete, because when the disk is manufactured, the molecules have a random orientation, and using an AC electromagnet comes closest to randomizing the molecules, again.       
A: Conservation of information in quantum mechanics is a hypocrisy as much as it is so in classical mechanics. It is not conserved in the same sense as energy, charge, or momentum. When sages like Hawking and Penrose discuss whether does “information” survive destruction in a spacetime singularity, they mean something utterly different from the concept familiar to an information engineer.
Reconciliation of conservation laws with quantum uncertainty is not an easy thing. But energy, charge, and momentum are observable. We can speculate about quantum states with wider or narrower uncertainty of specific observables, but we can measure them. But which quantities are observed in quantum mechanics, how do they behave? The classification of physical quantities as intensive and extensive is well-known. Does some quantity behave like the average value over many parts of the space, or does it accumulate? Let us speak about traditional denotations as about space-intensive and space-extensive quantities, because the same line of thought can be applied to alternative quantum realities generated by a quantum measurement, instead of parts of 3-dimensional space. Observable quantities must be multiverse-intensive. It does not imply arithmetic mean values (in the sense of either probability theory or QFT), but the idea that measurement of an observable with uncertain value makes its possible values separated in different branches of the future, and doesn’t create completely new values.
Suppose that we had a particle initially with uncertain momentum and after the experiment this original momentum became more certain. There are possibly other cases, with other values of momentum, but different “versions” of experimenter can’t communicate; each of them sees its value (or range of values) of the original momentum. They do not split the original momentum in parts in the sense of addition, they split multiple values of it that were possible in the initial quantum state, possibly with different probabilities. Thus, momentum is multiverse-intensive, although space-extensive. That’s why we can observe it consistently.
Now, let us had a state of quantum computer (that supposedly contained an “information”) and effect a measurement. Was “information” conserved? Yes and no, depending on the point of view. Quantum Mechanics now has several “versions” of experimenter in superposition (so it was), whereas each “version” sees only its own piece of the original state (so it was not). Why can’t they communicate? A quantum informatist would say that shitdecoherence happened. So, “information” is multiverse-extensive. It conserved for Quantum Mechanics but a large part of it… disappeared for us, observers. We can’t observe this quantity consistently. There is no practical sense in the discussion about its conservation.
Okay, what do aforementioned quantum sages mean, indeed? They discuss whether are these quantum states with their treacherous superposition reliable in situations where the spacetime is destroyed itself. They might be or be not; it changes little in problems of overwritten disk drive or, say, human death.
Update:
I retract a half-baked (and apparently erroneous) statement about extensivity.
