Nest Next and Previous in a href with class that has a background image

EDIT

In single.php you should be using: <?php previous_post_link('%link', 'Previous'); ?> and <?php next_post_link('%link', 'Next'); ?>.
Then you add this to your functions.php:

function filter_next_post_link($link) {
    $link = str_replace("rel=", 'class="next" rel=", $link);
    return $link;
}
add_filter("next_post_link', 'filter_next_post_link');

function filter_previous_post_link($link) {
    $link = str_replace("rel=", 'class="prev" rel=", $link);
    return $link;
}
add_filter("previous_post_link', 'filter_previous_post_link');

Although this is not the answer to this question, but to paginate in categories you should be looking into next_posts_link_attributes and previous_posts_link_attributes hooks. Just add this to your functions.php:

function next_posts_link_css($content) { 
    return 'class="next"';
}
function previous_posts_link_css($content) { 
    return 'class="prev"';
}

add_filter('next_posts_link_attributes', 'next_posts_link_css' );
add_filter('previous_posts_link_attributes', 'previous_posts_link_css' );

Just to clarify. You’ll be using the usual pagination in your template files:

<?php previous_posts_link('Previous') ?>
<?php next_posts_link('Next') ?>