Nginx provides powerful rewrite commands in the servers' configuration, so it is flexible in its support for Clean URLs. The recommended settings from the Nginx Drupal Documentation are:
server {
     listen       80;
     location / {
         root   /path/to/drupal;
         index  index.php;
         error_page 404 = @drupal;
     location @drupal {
         rewrite ^(.*)$ /index.php?q=$1 last;
The key change is with the 404 line under location / and the location @drupalconfiguration section. This works by assuming that anything that isn't a reference to a specific file should be handled by Drupal via the rewrite rule.
If you are looking for more information about installing Nginx, see Installing Nginx With PHP5 (And PHP-FPM) And MySQL Support (LEMP) On Ubuntu 12.04 LTS.