Here's what is working for me:
# -*- coding: utf-8 -*-
from lxml import etree
from lxml.html import fromstring, HTMLParser
data = """<p>PR検索</p>"""
tree = fromstring(data, parser=HTMLParser(encoding='shift-jis'))
print etree.tostring(tree, encoding='shift-jis', method="html")
prints:
<p>PR検索</p>