The only package wkhtmltopdf required to print the reports has to be installed manually as the installation of this package is not managed automatically by the Odoo package installation process. The default version of wkhtmltopdf that is available in Debian repositories does not support headers and footers, so it cannot be installed automatically.
The recommended version is 0.12.1, and it is available on the wkhtmltopdf download page in the Archive section. Select the package based on the version of Ubuntu you have installed:
As there is no official release for Xenial Xerus, you can use the package available for Trusty Tahr. Download the installation file using the gdebi manager for better dependency management.