I've started development on a project (which used CVS) by downloading its sources, creating a fresh HG repository, and using that. However, the original project now has converted to using Mercurial as well. Can I add its history before my initial commit into my repository?
Alternately, how can I push my repository to the remote one so as to preserve the history of both?
You can't change the ancestors of your current repo without altering the hash id's of every changeset, which essentially makes it a different repo. The hash of "left-parent" and "right-parent" are part of "who a changeset is" and so giving a parent to the first parent-less changeset in your current repo would change that first changeset's hash, which since it's the parent of the second changeset would change it's hash and so on.
If you're okay with changing the hashes of your existing repo (which you shouldn't be if anyone else out in the wild has clones of it) you could use the convert extension or even just import/export to attach your repo to the their newly converted repo.