How to fix permalinks not working with Vagrant and WordPress?

Solution:

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

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

After that, the permalinks started working.