The first method is using git-cvsimport which in turn uses cvsps to convert CVS updates to patchsets which are then imported into git. This method works fairly well except that it does not import empty tags and branches, only tags and branches which have actual commits. I do most of my development on RHEL5, so I use EPEL5 to get git, git-cvs (for git-cvsimport) and cvsps.
The second method uses cvs2git, part of the cvs2svn suite for converting CVS repos to SVN and other SCMs (such as mercurial/hg). The code is available via SVN:
svn co http://cvs2svn.tigris.org/svn/cvs2svn/tr
This is implemented as a python script so python is required too.
Step 1 - create your cvs2git.options file - just copy the boilerplate cvs2git-example.options
Step 2 - run cvs2git - this will create two files cvs2git-tmp/git-blob.dat and cvs2git-tmp/git-dump.dat
Step 3 - create an empty git repo
mkdir proj.git
cd proj.git
git init
Step 4 - use git-fastimport to import the blobs
cd proj.git
cat ../cvs2git-tmp/git-blob.dat ../cvs2git-tmp/git-dump.dat | git fast-import
This method did import all tags and branches, including empty ones. One weird thing was that the proj.git directory was initially empty after the fast import - I guess it had to rebuild the indexes. But when I did a "git checkout master" all of the files showed up.
I'm not sure if the latter method can be used for incremental sync, so I'll probably go with the second method to create the initial git repo, and use the first method to sync incremental changes made to the CVS repos during the migration phase.