Update 2014: This post is educational, but rather obsolete given the current version of WordPress which handles the .htaccess file and rewrite rules automatically. If you enjoy learning, read on.
If you have a shared web hosting plan like I do with 1&1 Webhosting, you most likely do not have direct access to the computer which your website is hosted on to install and configure the mod_rewrite plugin for Linux/Apache or the ISAPI_Rewrite plugin for Windows/IIS, either one of which is required to get Permalinks working in WordPress.
However, there is another way to this by editing the .htaccess file in your root WordPress directory.
Download the .htaccess file from your root WordPress directory via FTP and open the file in a text editor.
Here is what my .htaccess looked like in Notepad before the modification to enable Permalinks:
AddType x-mapp-php5 .php # BEGIN WordPress # END WordPress
And here is what the modified version looks like, which enables some URL rewriting that WordPress requires to make proper use of Permalinks:
AddType x-mapp-php5 .php # BEGIN WordPress <IfModule mod_rewrite.c> ErrorDocument 404 /index.php?error=404 RewriteEngine On RewriteBase / RewriteCond %{REQUEST_FILENAME} !-f RewriteCond %{REQUEST_FILENAME} !-d RewriteRule . /index.php [L] </IfModule> # END WordPress

Just upload the .htaccess file back to your root WordPress directory via FTP, overwriting the old one.
Logon to your WordPress backend and go to Settings » Permalinks. Select the Custom option, then enter the following:
/%postname%/
What this does is effectively rewrite the URL for your posts to use the Post Name in the URL instead of the Post ID.
Using this article as an example, my previous URL of:
http://www.glassocean.net/?p=858
Would now become:
http://www.glassocean.net/how-to-enable-permalinks-in-wordpress-for-a-shared-web-hosting-plan/
As you can see, that is quite a long URL! You can shorten these URL’s by changing the Post Slug in the Post/Page editor.
Your solution doesn’t work my friend. I have a shared hosting on IIS7 ….tried using your solution. When I visit my site at the root it shows 404 message. When I suffix it with Index.php..it show my blog.