Permalinks en WordPress es la funcionalidad que permite tener URLs semánticas o más bonitas. Pasar de tener algo como example.com/article?=123456 a example.com/articulo-genial es posible activando los Permalinks.
En WordPress.com es muy sencillo tenerlos ya que vienen activados por defecto, sin embargo, en instalaciones propias de este CMS se necesitan algunos elementos activados en el servidor. Veamos.
Archivo .htaccess
Este archivo debe estar localizado en la carpeta raíz donde se instala el WordPress y debe tener estas líneas de código
Es importante que los permisos de este archivo sean 644.
Apache.conf
Debes haber activado antos la opción mod_rewrite lo que se logra con el comando:
sudo a2enmod rewrite
Luego hay que reiniciar el servidor con:
sudo service apache2 restart
En el archivo de configuración de Apache es importante que estén permitidos los enlaces simbólicos y la opción AllowOverride activada. Así deberían lucir esas líneas en tu archivo de configuración de apache (eso si tienes permiso a ver el archivo en el servidor)
Options FollowSymLinks AllowOverride All
Teniendo todo eso, los Permalinks deberían funcionar.
Para más detalle, la documentación oficial de los Permalinks en WordPress y un hilo de Stack Over Flow al respecto.