Para habilitar o mod_rewrite no Ubuntu (incluindo Ubuntu Server), entre no terminal e digite:

sudo a2enmod rewrite

sudo ./etc/init.d/apache2 force-reload

Está pronto!