Unlike adding a file, adding a new directory is done in one step; there's no need to do a commit afterwards:
floss$ mkdir c-subdir floss$ cvs add c-subdir Directory /usr/local/cvs/myproj/c-subdir added to the repository floss$
If you look inside the new directory in the working copy, you'll see that a CVS subdirectory was created automatically by add:
floss$ ls c-subdir CVS/ floss$ ls c-subdir/CVS Entries Repository Root floss$
Now you can add files (or new directories) inside it, as with any other working copy directory.