I tried to enable the fancy permalinks in WordPress. But all I got was an error 404: Page not found.

That is because for these fancy links WordPress maps the title and date of the article in the address to the original address example.com/?p=xyz by using the Apache module mod_rewrite. In Debian Lenny this is disabled by default. To activate it you just do a
# a2enmod rewrite
Additionally, AllowOverride has to be set to all instead of none. Modify the concerning file, e.g. /etc/apache2/sites-available/default:

<Directory /var/www/blog/>
...
AllowOverride all
...
</Directory>