In concept removing directories is somewhat similar to removing files--you want the directory to not exist in your current working directories, but you also want to be able to retrieve old releases in which the directory existed.
The way that you remove a directory is to remove all the files in it. You don't remove the directory itself; there is no way to do that. Instead you specify the -P option to cvs update or cvs checkout, which will cause cvsnt to remove empty directories from working directories. (Note that cvs export always removes empty directories.) Probably the best way to do this is to always specify -P; if you want an empty directory then put a dummy file (for example .keepme) in it to prevent -P from removing it.
Note that -P is implied by the -r or -D options of checkout. This way cvsnt will be able to correctly create the directory or not depending on whether the particular version you are checking out contains any files in that directory.