Changeset evolution doesn't actually delete the entries in the history log. Rather it is a commit that changes what history looks like at a certain point in time. There are CLI commands to show the commits that are actually obsolete or have been rewritten.

Since it's really a commit that changes what history looks like, it's safe to push to other users.

More details here: http://mercurial.selenic.com/wiki/ChangesetEvolution