Actually, they're not removed at all from your HD. The space is simply flagged to be made free to save new things onto. It's quite easy to recover deleted files if you haven't overwritten them.
Secure operating systems will overwrite freed-up blocks in order to reduce the possibility of recovering data, though most don't since it can cause quite a performance hit. Which is admittedly rather pedantic since most PC users won't be running at that sort of security level!
It is sometimes possible to recover data even after it's been overwritten, as already mentioned, though I suspect that the majority of anecdotal retellings of such occurrences are simply that.
As for the disk/disc thing, that's largely a US/non-US spelling difference; though there's a sort of unwritten standard suggesting one means magnetic and the other means optical in much the same way as the program/programme spelling referring to computer instructions and television shows respectively, it's a bit hazardous to make assumptions, though I probably only say that as I write "hard dis
c" since I think "disk" looks weird.