What you’re looking for is an endpoint. There are already several of these built in: /feed/some-feed/ for feeds or /trackback/ on posts. Those are both endpoints.
Fortunately, WordPress provides a handy function makes adding your own endpionts really easy. add_rewrite_endpoint
This is all the code you need to make your yearly category archives work:
<?php
add_action( 'init', 'wpse31422_init' );
function wpse31422_init()
{
add_rewrite_endpoint( 'year', EP_CATEGORIES );
}
As a plugin: https://gist.github.com/1296860
It works exactly like Stephen Harris’ answer, and you can reach a yearly, category archive by visiting yoursite.com/category/some-cat-slug/year/2011/.
Adding an endpoint creates a query variable with the same name as the first argument of the add_rewrite_endpoint function. In this case, year. Because this query var already exists in WP (to take care of the data-based archives), we don’t really have to do anything special here.