How can I recover a removed file in Mercurial (if at all)?

First, use hg grep to find the deleted file you wish to recover. The output of this command will show you the last revision for which the file was present, and the path to the deleted file. Second, run hg revert -r <revision number> <path to deleted file> The deleted file will now be in your working copy, ready to be committed back into head.

Quote from comment:

I set up a repository, committed all, Removed and then committed again

If this is the case then you just need to update the working directory to the previous revision:

$ hg update -C -r-2

Note the negative revision number. If the files you deleted aren't in the previous revision, you can find them by using:

$ hg log -v

For Mercurial 1.6 and above

If you know the name of the delete file you can find its revision easily with:

hg log -r "removes('NAME.c')"

This will give you the revision in witch a file called NAME.c (in the root) is deleted.

Then you can revert the file to the previous revision with (like other answers):

hg revert -r <revision number> <path to deleted file>

You can use a file name pattern instead to adapt to what you know, for example you can use **/NAME.c to search in all directories. You can read about it in File Name Patters. And use this link to know about the new revset specifications.