Подключаем сам модуль, в консоли:
sudo a2enmod rewrite

Редактируем конфигурацию хостов:
sudo nano /etc/apache2/sites-available/default

А именно, изменяем параметр AllowOverride None на AllowOverride All

Перезапускаем web-сервер:
sudo invoke-rc.d apache2 restart

Готово.

http://dig.org.ua/2008/01/26/mod-rewrite-on-apache2-in-ubuntu/