If you simply run:
git add -u
git will update its index to know that the files that you've deleted should actually be part of the next commit. Then you can run "git commit" to check in that change.
Or, if you run:
git commit -a
It will automatically take these changes (and any others) and commit them.
Update: If you only want to add deleted files, try:
git ls-files --deleted -z | xargs -0 git rm
git commit