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;
     server_name  example.org;
     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.
Of course, you have to enable PHP by inserting the following codes:
        location ~ \.php$ {
                fastcgi_split_path_info ^(.+\.php)(/.+)$;
                # fastcgi_pass 127.0.0.1:9000;
                # With php5-fpm:
                fastcgi_pass unix:/var/run/php5-fpm.sock;
                fastcgi_index index.php;
                include fastcgi_params;
        }

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.