It’s easy if all posts are shown on the same page, then you can do:
$AZposts = get_posts(array(
'numberposts' => -1,
'post_type' => 'post',
'orderby' => 'title',
'order' => 'ASC',
'category' => $cat
));
$current = "";
$nav = "";
$postlist = "";
foreach($AZposts as $AZpost) {
$firstletter = strtoupper(substr($AZpost->post_title,0,1));
if($firstletter != $current) {
$postlist .= "<b><a name="$firstletter"> $firstletter </a></b><br>\n";
$nav .= "<a href="#$firstletter"> $firstletter </a> ";
$current = $firstletter;
}
$postlist .= $AZpost->post_title . "<br>\n";
}
print $nav . "<br>" . $postlist;