I should not have posted it so fast.
ad. 2) The problem is a bit different - the base url is all right, but the links are leading to http://localhost/cgi-bin/search/brewery/list instead of http://localhost/cgi-bin/search/beer.pl/brewery/list
ad. 3) This was my mistake of course. Apache perl was not finding BeerDB in it's path.