WordPress is having custom permalink feature where you can provide the way you want the permalink on your site. The default one is blog_url/?p=post_id. On the permalink structure page under settings panel, you can choose to have date, post title, category, post_id etc. in the permalink structure. With a small change in .htaccess file, your new permalink structure will be implemented. Having post_id and the post_title in permalink structure is fine but there is some performance problem with category in permalink structure.
In WordPress 3.3, development team has rectified the issue and you will not have any problem in having category_slug in the permalink structure of the WordPress site. According to the team,
You have more freedom when choosing a post permalink structure. Skip the date information or add a category slug without a performance penalty
Actually the rewrite rules were generated inconsistently for the permalink structure of /%category%/%postname%. Now the problem has been solved and after editing the post.php core file, they have achieved the expected result. So from WordPress 3.3 and onwards, you can use Category in the permalink structure without worrying about the performance issue.
WordPress 3.3 Release Candidate 3 is available for testing purpose. It is expected that WordPress team will release the final version of WordPress 3.3 in first week of January. There are only 3 open tickets in WordPress 3.3 milestone on Trac as they have closed 581 till now.