Then, perform a commit:

# cvs commit

Here comes the trick. Perform the following steps to delete the directory:

# cd ..
# cvs remove mydir
# rm -rf mydir

Notice that removing the directory didn't require another commit -- directories are added to and removed from the repository in real-time.