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.