Eigentlich bleibt diese Thematik immer irgendwie im Hintergrund weil es auf den meisten Servern ohne Probleme funktioniert die Permalinkstruktur von WordPress anzupassen.
Soltle es dann einmal nicht funktionieren geht natürlich die große Fehlerdiagnose los.

Ich versuche hier mal ein wenig zu erläutern, wie man die Permalink Struktur am besten anpasst.
Zu erst der ein kurzer Blick ins Rootverzeichnis. Sollte sich dort keine .htaccess-Datei befinden so erstellt man auf dem Desktop (oder irgendwo anders lokal) eine neue Textdatei, nennt diese htaccess.txt.
In diese Textdatei schreibt man nun folgenden Inhalt:

<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]</ifmodule>

Somit hat man gleich zwei Fliegen mit einer Klappe geschlagen. Zum einen hat man die Rewrite Engine für den Server aktiviert und zum zweiten hat man das nervige “index.php” aus der Permalink Struktur gestrichen, welches Worpdress seit der Version 2.2.2 in die URL einbettet.
aus: http://www.ihredomain.tld/index.php/verzeichnis wird http://www.ihredomain.tld/verzeichnis.
Jetzt kann man natürlich auf vorgegebene Permalinkstrukturen zurückgreifen oder nutzt die Benutzerdefinierte Struktur.
Ich persönlich bevorzuge folgende, benutzerdefinierte:
/%category%/%postname%/.
Natürlich muss man vorher die htaccess.txt auf ins Rootverzeichnis des Servers kopieren und anschließend in .htaccess umbennen.