The marked answer has the problem that the available packages on the machine that is doing the downloads might be different from the target machine, and thus the package set might be incomplete.
To avoid this and get all dependencies, use the following:
apt-get download $(apt-rdepends <package>|grep -v "^ ")
Some packages returned from apt-rdepends don’t exist with the exact name for apt-get download to download (for example, libc-dev). In those cases, filter out those exact names (be sure to use ^<NAME>$ so that other related names, for example libc-dev-bin, that do exist are not skipped).
apt-get download $(apt-rdepends <package>|grep -v "^ " |grep -v "^libc-dev$")
Once downloaded, you can move the .deb files to a machine without Internet and install them:
sudo dpkg -i *.deb