Template :

<template id="website.previous_and_next" name="Previous and next">
<div id="previous_and_next_iv" t-if="pager_pt['products_count'] > 1">
<a 
   t-att-class=" 'btn btn-primary pull-left mt10 mb10 disabled' if pager_pt['product']['num'] == 0 else 'btn btn-primary pull-left mt10 mb10' "
   t-att-href="pager_pt['product_previous']['url']" >
Previous product in this category</a>
<a
   t-att-class=" 'btn btn-primary pull-right mt10 mb10 disabled' if pager_pt['product']['num'] == pager_pt['products_count'] else 'btn btn-primary pull-right mt10 mb10' "
   t-att-href="pager_pt['product_next']['url']" >
Next product in this category</a>
</div>
</template>

Where you want to put the buttons :

<template id="website_sale.product" name="Product">      
  <t t-call="website.layout">
[...]
   <div class="row previous_and_next_iv">
   <t t-call="website.previous_and_next" />
   </div>
[...]
</template>

Python code to override :

class website_sale_all(website_sale):    

    @http.route(['/shop/product/<model("product.template"):product>'], type='http', auth="public", website=True)
    def product(self, product, category='', search='', **kwargs):
        cr, uid, context, pool = request.cr, request.uid, request.context, request.registry
        category_obj = pool['product.public.category']
        template_obj = pool['product.template']
        context.update(active_id=product.id)                
        if category:
            category = category_obj.browse(cr, uid, int(category), context=context)
            category = category if category.exists() else False
            
        attrib_list = request.httprequest.args.getlist('attrib')
        attrib_values = [map(int,v.split("-")) for v in attrib_list if v]
        attrib_set = set([v[1] for v in attrib_values])
        keep = QueryURL('/shop', category=category and category.id, search=search, attrib=attrib_list)
        category_ids = category_obj.search(cr, uid, [], context=context)        
        category_list = category_obj.name_get(cr, uid, category_ids, context=context)
        category_list = sorted(category_list, key=lambda category: category[1])
        pricelist = self.get_pricelist()
        from_currency = pool.get('product.price.type')._get_field_currency(cr, uid, 'list_price', context)
        to_currency = pricelist.currency_id
        compute_currency = lambda price: pool['res.currency']._compute(cr, uid, from_currency, to_currency, price, context=context)        
        domain = self._get_search_domain(search, category, attrib_values)
        url = "/shop/product"
        product_obj = pool.get('product.template')        
        product_count = product_obj.search_count(cr, uid, domain, context=context)        
        product_ids = product_obj.search(cr, uid, domain, limit=200, order='website_published desc, website_sequence desc', context=context)
        if category:
            cat_id = category.id
        else:
            cat_id = ''
            
        pager_pt = request.website.pager_pt(active_product=product.id, products=product_ids, active_category=cat_id)
        products = product_obj.browse(cr, uid, product_ids, context=context)        
        if not context.get('pricelist'):
            context['pricelist'] = int(self.get_pricelist())
            product = template_obj.browse(cr, uid, int(product), context=context)
        values = {
            'search': search,
            'category': category,
            'pager_pt': pager_pt,
            'pricelist': pricelist,
            'attrib_values': attrib_values,
            'compute_currency': compute_currency,
            'attrib_set': attrib_set,
            'keep': keep,
            'category_list': category_list,
            'main_object': product,
            'product': product,
            'get_attribute_value_ids': self.get_attribute_value_ids
        }
        return request.website.render("website_sale.product", values)    
        
        
        
from openerp.addons.website.models.website import website
class website_iv(osv.osv):
    _inherit = "website"    
    
    def pager_pt(self, cr, uid, active_product, products, active_category, context=None):        
        products_count = len(products)        
        num_product = products.index(active_product)        
        num_previous = num_product - 1        
        num_next = num_product + 1        
        num_min = 0        
        num_max = products_count - 1        
        def get_url(id):
            if active_category:
                _url = "/shop/product/%s?category=%s" % (id, active_category) #if page > 1 else url
            else:
                _url = "/shop/product/%s" % (id)
            return _url        
        retour = {
            "products_count": products_count - 1,          
            "product": {
                #'url': 'asdfasdF', #get_url(active_product),
                'num': num_product
            },            
            "product_previous": {
                'url': get_url(products[max(num_previous, num_min)]),
                'num': num_previous
            },
            "product_next": {
                'url': get_url(products[min(num_next, num_max)]),
                'num': num_next
            },
        }
        return retour