There are lots of tutorials regarding how to set up permalinks on a WordPress site but generally, they’re tutorials for how to achieve this on an Apache web server under Linux.
This is one (http://heartdrops.org/tutorials/wp-removing-index-php-in-urls/) I really liked because it’s written for the common user. Simple steps, what you need, easily understandable. Unfortunately, it didn’t work for me (cuz it’s not for Windows hosting).

My solution is not unique, it comes from: http://wordpress.org/support/topic/permalinks-not-working-on-windows-server. Unfortunately, it was difficult to find so I was working on this problem for more than a few hours. (#$&^(%^#!)

Purpose of this tutorial
To achieve the following structure in WordPress URLs
http://www.worldofwarren.com/tutorials/setting-up-wordpress-permalinks/
or
http://www.worldofwarren.com/setting-up-wordpress-permalinks/

instead of, by default,
http://www.worldofwarren.com/index.php/tutorials/setting-up-wordpress-permalinks/
or
http://www.worldofwarren.com/index.php/setting-up-wordpress-permalinks/

What you need to know/have
PHP knowledge
A text editor
Access to your site’s 404, 404.2, and 404.3 errorpages

Procedure

1. Create a simple new document file called wp-404-handler.php and place it in the root directory of your site.
2. Place the following code inside wp-404-handler.php
   <?php
   // This is the default file for the site. Usually index.php
   $default = ‘index.php';

   // The name of this file.
   // Set this value for the URL in Custom Error Properties of your website in IIS.
   // Goto: IIS Manager > Websites > [Site Name] > Properties > Custom Errors >
   // 404 & 404;2 & 404;3 > URL (Requires a ‘/’ prefix in IIS).
   $thisfile = ‘404-handler.php';

   $_SERVER[‘ORIG_PATH_TRANSLATED’] = str_replace($thisfile, $default, $_SERVER[‘ORIG_PATH_TRANSLATED’]);
   $_SERVER[‘SCRIPT_FILENAME’] = str_replace($thisfile, $default, $_SERVER[‘SCRIPT_FILENAME’]);
   $_SERVER[‘ORIG_PATH_INFO’] = str_replace($thisfile, $default, $_SERVER[‘ORIG_PATH_INFO’]);
   $_SERVER[‘SCRIPT_NAME’] = str_replace($thisfile, $default, $_SERVER[‘SCRIPT_NAME’]);
   $_SERVER[‘PHP_SELF’] = str_replace($thisfile, $default, $_SERVER[‘PHP_SELF’]);
   $_SERVER[‘PATH_INFO’] = false;

   $qs =& $_SERVER[‘QUERY_STRING’];
   $ru =& $_SERVER[‘REQUEST_URI’];
   $pos = strrpos($qs, ‘://’);
   $pos = strpos($qs, ‘/’, $pos + 4);
   $_SERVER[‘URL’] = $ru = substr($qs, $pos);
   $qs = trim(stristr($ru, ‘?’), ‘?’);

   // Required for WordPress 2.8+
   $_SERVER[‘HTTP_X_ORIGINAL_URL’] = $ru;

   // Fix GET vars
   foreach ( $_GET as $var => $val ) {
     if ( substr($var, 0, 3) == ‘404’) {
       if ( strstr($var, ‘?’) ) {
         $newvar = substr($var, strpos($var, ‘?’) + 1);
         $_GET[$newvar] = $val;
       }
     unset($_GET[$var]);
     }
     break;
   }
   include($default);

   ?>

3. Configure the 404, 404,2 and 404.3 error pages to point to the URL: /wp-404-handler.php
   (in this case, http://www.worldofwarren.com/wp-404-handler.php)
4. Finally, in your WordPress permalinks section, add the follow to the Custom Structure.
   /%category%/%postname%/
   (though /%postname%/ might be more common).
   

My ramblings
It seems a bit odd WordPress would think users would want index.php in their URLs. They look hideous.