Just got the permalink structure working. Had to put
Options +FollowSymLinks
into the .htaccess file in the root directory of the blog.
Also installed a sitemap builder plugin to help search engines grok the site. Now I am checking with Google Webmaster Tools whether google crawls correctly.