How to checkout old git commit including all submodules recursively?

You need two commands to achieve this:

git checkout *oldcommit*
git submodule update --recursive

Update: This answer is outdated as of 2018 – see VonC’s answer below for more current information.