URL routing with Joomla's framework is a very tricky job, that involves a lot of planning ahead with your component's development, compromises on flexibility and taming error sources that go with using URL routing. To round things up, there is very little documentation (at least I didn't find much) about the process.
On the up-side, it is very rewarding and the right approach to SEF (let alone the fact that all these SEO plugins out there are very thoughtful but will always be a p.i.t.a. for the end user, performance and ultimately for the developer).
The idea of the Joomla router.php files is simple in general:
One __parseRoute() function
One __BuildRoute() function
__parseRoute is used to translate the SEF URL to a key-value pair.
It receives "segments" as referenced parameter in form of an array with the numeric keys (which is the order of the segments in the URL), representing the pieces in the URL that Joomla does not handle. It should return an associative array with the keys representing the query parameter keys and the values representing the values of the query parameters (e.g. array('myparam'=>'myvalue')).
__buildRoute is doing the opposite. It is used to build the SEF URL that is used for any href dealing with your component. URLs in your component should use JRoute::_('nonsef string'); in order to get built.
It takes the query parameters as referenced associative array including those that Joomla handles (Joomla handles parameters like 'option', 'tmpl', 'Itemid' etc) and should return URL segments in form of an numeric array, where the keys represent the order in which the URL segments should appear in the URL and the values represent the text that should appear in the URL. Every item in the query array that was translated into a segment has to be unset (e.g. unset($query['myparam']), or it will be appended to the URL as normal query parameter. You can leave out some parameters if you decide not to SEFify it.
That's the whole thing. How you return your values for parsing and building is entirely up to you and you got the whole Joomla framework at your disposal (like JFactory, JRequest, JSite, but note that you have to take performance in consideration since there might be lots of links to parse for a page.
Also take into account that URLs pointing to your component do not necessarily have to be parsed when your component is loaded, so do not rely on any of your PHP classes already loaded.
A very useful method is to deal with performance issues for building routes is to have your non SEF parameter values use so called slugs (e.g. index.php?option=com_mycomponent&view=myview&content_id=2:myalias). Here, the alias (which you can use as segment) is already there, so you don't have to process the id and lookup the alias. In order not to break non-SEF configurations, you can use the recommended JRequest::getInt('[parameter]') method for integers, which returns your parameter value without the ':myalias' part as a nice by-product of proper input sanitation.
Note: This article is about Joomla 1.5, Joomla 1.6 does not necessarily works the same way.