The extremely useful mod_rewrite or rewrite module is not enabled by default on a new Apache web server install. Luckily, this turns out to be pretty simple to rectify.
Using the a2enmod function, simply run:
sudo a2enmod rewrite
sudo /etc/init.d/apache2 restart
The first line will enable the rewrite module (which should already be available) and the next restarts the apache web server to reflect the new module addition.
Nifty.