A: 

You could try adding a rewrite rule similar to this

rewrite ^/(.*)/?$ /index.php/$1 break;

Sorry, it's untested, but it should be close. More info: http://wiki.nginx.org/NginxHttpRewriteModule

mellowsoon
A: 

I have some experience with nginx in this regard and have even written about it. So in a shameless act of self-promotion here is the result of my earlier research:
http://www.magentocommerce.com/boards/viewreply/211050/

clockworkgeek
I came across your config file while googling the answer, but took only parts of it to use in mine. I'll try to see if using the config file as is will make a difference.
Cahit
I pretty much copied the whole config file shown in the thread, but I still get domain.com/index.php/category/product.html. I.e., it didn't work... Do you know why that might be the case?
Cahit
In the admin, under System > Configuration > Web > Search Engine Optimization you still need to turn on rewrites. This is true for all servers.
clockworkgeek
That did the trick! Thank you very much...
Cahit