In the past few months I have setup and helped others install and configure WordPress blogs many times. One of the more frequent questions I get pertains to this page in the WordPress admin labeled permalinks. The easiest way to describe permalinks is by saying that they are pretty URLs. For example, enabling permalinks on your WordPress blog changes http://www.yourdomain.com/index.php?p=102 to something like the following URL: http://www.yourdomain.com/2006/04/30/apple-releases-ipod-micro (although permalinks can be setup to display in various formats).
Permalinks work by adding an entry into a .htaccess file, which lies at the root public html directory of your server (this might be a folder named httpdocs, www, public_html, etc. - it should be obvious). This is a powerful config file or "distributed configuration file" that can carry out actions in the Apache webserver on a per-directory basis. Permalinks usually rely on mod_rewrite, part of Apache, to turn the post ID URL into the nicer URLs you see on this site. Below is what the typical .htaccess file for a permalink-enabled WordPress blog looks like.
I don't want to delve into the world of .htaccess hacking but I will mention that if you add to it, such as making a custom error page, make sure to have that outside of the # WordPress tags completely. Anything in between those two will get overwritten anytime you add a page to your blog or make changes in the WP admin affecting permalinks (hat tip to Kristin for the reminder).
Set Them Up
Before I go about professing the sheer joys of using permalinks, let's make sure your blog can strut permalinks. Login to your server and navigate to the aforementioned public web directory. Make a new, blank plain text file (none of that .rtf or .doc stuff) in that directory and label it .htaccess; the dot is very important. You might need to have your FTP client set to show invisible files or not hide them - a quick peek in the options should solve this. Now right-click on this file and select get info or some option with chmod, this varies by FTP client so I can't cover all the bases. We are going to want to perform a chmod 777 so that we can change options in WordPress and let it have the ability to write to the file. Once you have done that, login to your WordPress admin and go to Options » Permalinks. You will be confronted with a few options as to how you want to format your permalinks. The most widely used format is date and name based, however you can pick whichever you like. When you've selected the format, just click on Update Permalink Structure. Now go back to your FTP client and perform a chmod 644 to ensure that nothing bad can happen to your omnipotent .htaccess file from outside sources. You're done!
If you receive any Error 500: Internal Server Error, this is most likely from a botched .htaccess configuration. Go back and ensure that your file was chmod 777'd before enabling permalinks and then try it again. Other sources of this error can arise from a reluctant server or one that doesn't support mod_rewrite in Apache.. or your server doesn't even run Apache. In this case, a visit to the WordPress Codex is in order for setting up permalinks in your special case.
Come On, Enlighten Us Already
Permalinks encourage website browsing. From a millisecond glance at a link to your permalinked blog, the user knows how recent the post is and its title. That is a lot more than /index.php?p=102 could ever convey. What if a user follows a permalink to your site only to find that you have since removed that article or changed the post slug (the last part of the permalink with the title)? They can simply navigate your archives by manipulating your URL. For example, going to http://www.paulstamatiou.com/2006/01 produces an archive page letting the user browse all of the posts I made in January, 2006. Want to see what post I made on January 21st, 2006? Just add /21 to the end of the URL.
Permalinks are vital to a successful blog. By only remembering the date of a post, people can easily spread the word about a particular post of yours. Permalinks also work for categories and tags. You can see all of my posts in the software category with a URL formatted like http://www.paulstamatiou.com/categories/software/. Also, since the actual post title is within the link itself, search engines pick up your link faster and can provide your link in higher search rankings. Tom Raftery goes more in-depth about the relationship between SEO and Permalinks.