<?php

// Get the oldest post in this category
// This will tell us how many years we need to go back
$oldest = get_posts( array(
    'category_name'  => get_query_var( 'category_name' ),
    'orberby'        => 'date',
    'order'          => 'ASC',
    'posts_per_page' => 1,
) );

// Build the array of years to show (oldest -> now)
$years = range( get_the_time( 'Y', $oldest->ID ), date( 'Y', current_time( 'timestamp' ) ) );

// Loop through the years and output the posts for that year
echo '<ul>';
foreach ( $years as $year ) {

    // Get this year's posts
    $year_posts = get_posts( array(
        'category_name'  => get_query_var( 'category_name' ),
        'year'           => $year,
        'posts_per_page' => -1, // All posts
    ) );

    if ( ! $year_posts )
        continue; // No posts for this year

    echo "<li>$year<ul>";

    foreach ( $year_posts as $year_post ) {
        echo '<li><a href="' . esc_url( get_permalink( $year_post->ID ) ) . '">' . get_the_title( $year_post->ID ) . '</a></li>';
    }

    echo '</ul></li>';<ul><li>post 1 from 2011</li><li>post 2 from 2011</li></ul><li>2010</li><ul><li>post 1 from 2010</li><li>post 2 from 2010</li></ul></ul>
}
echo '</ul>';