Permalinks not working with Vagrant

I solved the problem myself.

In the default apache configuration, under /etc/apache2/sites-enabled, where mine is called 15-default.conf

This was declared under the document root:

   <Directory "/var/www">
     Options Indexes FollowSymLinks MultiViews
     AllowOverride None
     Order allow,deny
     Allow from all
   </Directory>

I had to change AllowOverride None to AllowOverride All. Thus you’ll get the following:

   <Directory "/var/www">
     Options Indexes FollowSymLinks MultiViews
     AllowOverride All
     Order allow,deny
     Allow from all
   </Directory>

After that, the permalinks started working.