You will need to intercept the links generated by WordPress and append the query var onto the relevant URLs.
You can do this quite easily with a filter on category URLs with something like...
function add_my_query_var( $link ) {
$link = add_query_arg( 'sort', 'most_voted', $link );
return $link;
}
add_filter('category_link','add_my_query_var');
I also spotted this handy list of filters on Mike's post on SO, it should cover all the possible URLs you'd want to tweak the query vars for...
add_filter('page_link','add_my_query_var');
add_filter('post_link','add_my_query_var');
add_filter('term_link','add_my_query_var');
add_filter('tag_link','add_my_query_var');
add_filter('category_link','add_my_query_var');
add_filter('post_type_link','add_my_query_var');
add_filter('attachment_link','add_my_query_var');
add_filter('year_link','add_my_query_var');
add_filter('month_link','add_my_query_var');
add_filter('day_link','add_my_query_var');
add_filter('search_link','add_my_query_var');
add_filter('feed_link','add_my_query_var');
add_filter('post_comments_feed_link','add_my_query_var');
add_filter('author_feed_link','add_my_query_var');
add_filter('category_feed_link','add_my_query_var');
add_filter('taxonomy_feed_link','add_my_query_var');
add_filter('search_feed_link','add_my_query_var');
add_filter('get_edit_tag_link','add_my_query_var');
add_filter('get_edit_post_link','add_my_query_var');
add_filter('get_delete_post_link','add_my_query_var');
add_filter('get_edit_comment_link','add_my_query_var');
add_filter('get_edit_bookmark_link','add_my_query_var');
add_filter('index_rel_link','add_my_query_var');
add_filter('parent_post_rel_link','add_my_query_var');
add_filter('previous_post_rel_link','add_my_query_var');
add_filter('next_post_rel_link','add_my_query_var');
add_filter('start_post_rel_link','add_my_query_var');
add_filter('end_post_rel_link','add_my_query_var');
add_filter('previous_post_link','add_my_query_var');
add_filter('next_post_link','add_my_query_var');
add_filter('get_pagenum_link','add_my_query_var');
add_filter('get_comments_pagenum_link','add_my_query_var');
add_filter('shortcut_link','add_my_query_var');
add_filter('get_shortlink','add_my_query_var');
add_filter('home_url','add_my_query_var');
add_filter('site_url','add_my_query_var');
add_filter('admin_url','add_my_query_var');
add_filter('includes_url','add_my_query_var');
add_filter('content_url','add_my_query_var');
add_filter('plugins_url','add_my_query_var');
add_filter('network_site_url','add_my_query_var');
add_filter('network_home_url','add_my_query_var');
add_filter('network_admin_url','add_my_query_var');
Hope that helps..
sort
in the URL when navigating away, in a category.