Both of these will stage all files, including new files (which git commit -a misses) and deleted files.
The difference is that git add -A also stages files in higher directories that still belong to the same git repository. Here's an example:
/my-repo
.git/
subfolder/