If you can possibly avoid using Windows hosting, do so. If you have to use it, there is still hope!
Here are some old posts dealing with pretty permalinks on IIS. You will need to be fairly confident at changing settings in your hosting account, and using FTP to upload and change files on your WordPress installation.
If you turn on pretty permalinks in Windows IIS, they will trigger a 404 error on your server, but if your hosting company will let you define a page to show for 404 errors, you can make it call a small php script which interprets the error and shows the correct page from your site.
I have WordPress 3.8 and the code works fine with that. I don’t know how it’ll effect SEO though, and only HTML5 browsers will show exactly the same urls as with Linux – hosted permalinks.
STEP BY STEP
1) Copy Kevin Newman’s php code WordPress.org thread and save it in a file called wp-404-handler.php . Upload it via FTP to the root directory of your webspace.
2) Turn on ‘Custom error pages’ in your hosting control panel. My hosting company is Fasthosts, and the screen looks like this:
I had to click the radio button to turn Custom Error Pages ON, enter /wp-404-handler.php in the textbox in the 404 section, then click Apply Settings. It took a while before the setting came into effect.
3) Log into your WordPress Dashboard. Click Settings->Permalinks and turn pretty permalinks on. IMPORTANT – WordPress knows you have an IIS server, so it will use ‘almost pretty’ permalinks by default. It’ll say /index.php/%postname%/ in the Custom Structure box – change this to just /%postname%/ and click Save Changes.
4) Try it. If you click on a post or category and you see the normal 404 page, you may need to wait a little for your changes to custom error pages to take effect.
Here’s the little script in my header.php file:
In HTML5 browsers, this script can rewrite the messy url to a pretty one without reloading the page.
So there’s the IIS implementation of pretty permalinks. To users of the site it will look exactly the same as a site running on Linux, but you may find that this solution hurts your SEO, and relative urls within your site might get broken.