Read up on Dynamic URLs and Apache mod_rewrite.
Also check this mod_rewrite rule generator out.
As an example of what mod_rewrite can do for you as far as descriptive URLs, The permalink might be thought of as the url:
http://www.somesite.com/catalog.php?cat=widgets&product_id=1234
And the rewrite module will create the much more descriptive and simpler:
http://www.somesite.com/catalog/widgets-1234.html
dynamically as needed. I am not sure if any of these mappings are cached server-side for future use, but I don't imagine it uses a huge amount of overhead to process the rules.
Here is the rule that did the above rewrite which is placed in a .htaccess file:
RewriteEngine On
RewriteBase /
RewriteCond %{QUERY_STRING} ^cat\=([^&]+)\&product_id\=([^&]+)$
RewriteRule ^$ /catalog/%1-%2.html [R=301,
This example was found here.
It does not take much overhead to dynamically generate a descriptive URL on the fly and have it serve the permalink content. I don't think they are worrying about storing or caching the rules in a database at all.
It seems to be highly recommended by SEO enthusiasts that you create a google sitemap.xml to assist in google indexing these (possibly infinite, or to the upper bound of URL length which is undefined but > 2000 char URL won't work in many browsers) statically generated pages. As long as the rules are deterministic they might as well be permalinks.