First, what is permalink ? Direct from Wikipedia :

A permalink is a URL that points to a specific blogging entry even after the entry has passed from the front page into the blog archives. Because a permalink remains unchanged indefinitely, its use avoids link rot. Most modern weblogging and content-syndication software systems, including Wordpress, Movable Type, LiveJournal, RapidWeaver, Pivot and Blogger, support such links. Other types of websites use permalinks, too, but the term itself is most common within the blogosphere. Permalink is a portmanteau word made from permanent link and is often simply stated so as to be human-readable.

Permalinks are very importnant and WordPress gives us the opportunity to customize them well. If you want to know more about how to use permalinks go to the following WordPress Codex page: Using Permalinks.

The default WordPress installation use’s this format: http://seoforwordpress.net/?p=123, but it is not good at all. What do the numbers in the end of permalink format mean to search engines… good question, but the answer is - nothing !

In the WordPress administration panel go to Options>Permalinks and select a permalink structure.

You can choose this permalink options:

Default
» http://seoforwordpress.net/?p=123

Date and name based
» http://seoforwordpress.net/2007/01/14/sample-post/

Numeric
» http://seoforwordpress.net/archives/123

Or custom, you can write your own, look at structure tags to create something original for yourself:

Structure Tags

%year%
The year of the post, four digits, for example 2004
%monthnum%
Month of the year, for example 05
%day%
Day of the month, for example 28
%hour%
Hour of the day, for example 15
%minute%
Minute of the hour, for example 43
%second%
Second of the minute, for example 33
%postname%
A sanitized version of the title of the post. So “This Is A Great Post!” becomes “this-is-a-great-post” in the URI (see note below)
%post_id%
The unique ID # of the post, for example 423
%category%
A sanitized version of the category name. Nested sub-categories appear as nested directories in the URI.
%author%
A sanitized version of the author name.

Most importantly, be sure that the post title is in the permalink structure you use. This is very impotant.

I use /%year%/%monthnum%/%day%/%postname%/ on this website, which is one of the best if you ask me