パーマリンクとはなんぞや？
すごく簡単に言うとURLの作られ方です。
通常ブログのパーマリンクは大体において年月日なんかをベースに生成されるのが一般的ですよね。こんな風に

http://monodez.com/2010/7/sample.html

でも僕はカテゴリーベースの構造の方が好きなんです。
例えば「WordPress」というカテゴリーに書いた記事なら

http://monodez.com/wordpress/sample.html

といった具合に。

メリットとしてはわかりやすさ。そして階層が浅くなることによるSEO効果。（英語圏ではURLにキーワードを入れるとSEO対策として効果があると言うが、日本語サイトではどうだろう？）
逆にデメリットとしては記事を別カテゴリーに移動した際にリンク切れが起こると。
つまりあとからカテゴリーを細分化する可能性があるならあまりおすすめはできません。

カテゴリーベースでの設定方法ですが、WordPressの管理画面から「パーマリンク設定」へ。
そこで『カスタム構造』の欄に以下のように書きます。

/%category%/%postname%.html

もちろんチェックを付けるのを忘れずに。
これで記事ページはOKなんですが、カテゴリートップのURLを見てみると何やらゴミが。

http://monodez.com/category/wordpress

「category」という部分はどう見ても余計ですよね。
こいつは『WP No Category Base』というプラグインで取り除いてしまいます。
手順は普通のプラグインと一緒。
ダウンロード、解凍して、/wp-content/plugins/にアップロード。
あとは管理画面で有効化するだけ。

これでOK。URLもすっきりスマートになりましたとさ。