The subject of exactly how tagging interacts with adding and removing files is somewhat obscure; for the most part CVS will keep track of whether files exist or not without too much fussing. By default, tags are applied to only files which have a revision corresponding to what is being tagged. Files which did not exist yet, or which were already removed, simply omit the tag, and CVS knows to treat the absence of a tag as meaning that the file didn't exist as of that tag.
However, this can lose a small amount of information.
For example, suppose a file was added and then removed.
Then, if the tag is missing for that file, there is no
way to know whether the tag refers to the time before
the file was added, or the time after it was removed.
If you specify the `-r' option to
then CVS tags the files which have been removed,
and thereby avoids this problem. For example, one
-r HEAD to tag the head.
On the subject of adding and removing files, the
cvs rtag command has a `-a' option which
means to clear the tag from removed files that would
not otherwise be tagged. For example, one might
specify this option in conjunction with `-F' when
moving a tag. If one moved a tag without `-a',
then the tag in the removed files might still refer to
the old revision, rather than reflecting the fact that
the file had been removed. I don't think this is
necessary if `-r' is specified, as noted above.