This is what I did:

1. Enable mod_rewrite in lighttpd.conf
2. Inside the block for your virtual host definition $HTTP["host"] == "youdomain.com" {...}, add
   url.rewrite-once = (
       "^/(files/.*)$" => "/$1",
       "^/system/test/(.*)$" => "/index.php?q=system/test/$1",
       "^/([^.?]*)\?(.*)$" => "/index.php?q=$1&$2",
       "^/([^.?]*)$" => "/index.php?q=$1",
       "^/search/node/(.*)$" => "/index.php?q=search/node/$1"
       )
   The first line tells Lighty not to translate anything start with /files. If you have other directories that serve static files, add them the same way.
3. If your baseurl is not "/", please change that accordingly.
4. Now restart your lighty and it shall work.

 This configuration works for Drupal-5 too.

Update: This article is probably a better reference for you: http://www.cyberciti.biz/tips/lighttpd-drupal-htacess-seo-clean-urls.html