Cache not working

I’m having troubles with my site being super slow. It seems like caching isn’t working. When I upload the site to a different server, everything seems fine.
When I empty the template cache and load the page, there are ~9000DB queries which take about 7s. On the page where the caching works, on the next page load only 55DB queries are necessary which take 2,6s.

The only differences I’m aware of now regarding the servers is, that the "slow" one is running with MySQL 5.5 and NGINX while the other uses 5.7 and Apache.

What needs to be installed or configured on the server for caching to work? I do use {% cache %} tags in the twig-code.