The instructions at http://codex.wordpress.org/Create_A_Network are good, and are mostly enough to get it up and running.
There are two more things to do on Ubuntu servers:
Enable mod_rewrite by issuing the command a2enmod rewrite in a terminal.
Open /etc/apache2/apache2.conf and find the part that says:
<Directory /var/www/>
Options Indexes FollowSymLinks
AllowOverride None
Require all granted
</Directory>
Replace AllowOverride None with AllowOverride All
That was all I had to change to get my site working on Ubuntu 16.04 LTS.