Directories are handled fundamentally different from ordinary files by CVS. They are not under revision control, i.e. you cannot tell which directories existed in the project at a certain time. Furthermore, directories can never be explicitly removed (expect by removing them directly in the repository).
As a substitute, CVS follows the convention that a directory is "not existent" in a version of the project if is is empty. This convention can be enforced by using the option -P to cvs update and cvs checkout. Cervisia always uses this flag.
A directory can be added to the repository with the command
cvs add dirname |
which is implied by the menu item File->Add to repository. Note that in contrast to adding files, adding directories does not require a commit afterwards.