Solution:
There is a very detailed summary in the WordPress Codex on Using Permalinks.
If you are interested in how it was implemented, see the WordPress Rewrite API in file /wordpress/wp-includes/rewrite.php
and check the related reference entry in WP Codex.