"Pretty" permalinks usually require
mod_rewrite, and IIS (common on
Windows servers) does not support
mod_rewrite.
Check Wordpress Codex, specifically Permalinks Without Mod Rewrite section since it has information about permalinks in your environment (some information below, check the link for full information since it's the official documentation):
If you are using IIS 7 and have admin
rights on your server, you can use
Microsoft's URL Rewrite Module
instead. Though not completely
compatible with mod_rewrite, it does
support WordPress's pretty permalinks.
Once installed, open the web.config
file in the WordPress folder and add
the following rule to the
system.webServer element.
<rewrite>
<rules>
<rule name="Main Rule" stopProcessing="true">
<match url=".*" />
<conditions logicalGrouping="MatchAll">
<add input="{REQUEST_FILENAME}" matchType="IsFile" negate="true" />
<add input="{REQUEST_FILENAME}" matchType="IsDirectory" negate="true" />
</conditions>
<action type="Rewrite" url="index.php" />
</rule>
</rules>
</rewrite>