In Git - with it's immutable changeset objects and mutable refs - I know that the original commits remain, which gives me a warm fuzzy feeling after an 'oops' "history rewriting" moment.
For example, after a "history rewriting" git rebase the original changesets (cbe7698, 09c6268) are still there and a new changeset (08832c0) was added. I can easily restore/access the other changesets until such a time as they are pruned.
$ git log --oneline --graph --decorate $(git rev-list -g --all)
* 08832c0 (HEAD -> master) Added bar and quxx to foo.txt
| * cbe7698 Added quxx to foo.txt
| * 09c6268 Added bar to foo.txt
|/
* 895c9bb Added foo.txt
Likewise, even a git commit --amend preserves the original/amended commit (d58dabc) and adds a new changeset:
$ git log --oneline --graph --decorate $(git rev-list -g --all)
* d9bb795 (HEAD -> master) Added cats and dogs to pets.txt
| * d58dabc Added cats to pets.txt
|/
* 08832c0 Added pets.txt
However, what happens in Hg after a "history rewriting" operation?
Do the original commits cease to exist? And if they still do exist, how can they be accessed and/or recovered?
It depends on whether you have the evolve extension installed or not. If you have the evolve extension installed, the only command that will actually remove revisions from the repository is hg strip; other commands leave the original commits in place, but hide them. You can see them with hg log --hidden (or other commands with the --hidden flag). If you want to get rid of them permanently, hg strip --hidden -r 'extinct()' can be used [1].
Most people, however, will just be using base Mercurial. In this case (and for hg strip even with evolve), the removed changesets will be stored as bundles in .hg/strip-backup. A Mercurial bundle is basically a read-only overlay repository; you can use hg log -R, hg tip -R, hg incoming, hg pull, etc. on it. This is all you need in principle, but it can be a bit cumbersome typing out the paths.
For convenience, Facebook has published a number of experimental extensions for Mercurial. Among them, the backups extension provides a convenience command (hg backups) that basically lists the commits in each bundle in .hg/strip-backup (similar to what hg incoming with an appropriate template would do) and hg backups --recover to pull in the changesets from the stripped commits (similar to what hg pull would do).
[1] Note that even then, a backup will be stored in .hg/strip-backup. If you want to get rid of them really permanently, you will also have to remove that backup.