Let's define a class like this:

class K(object):
    def __str__(self):
        return u'str'
    def __unicode__(self):
        return 'unicode'

print(repr( str(K()) ))
print(repr( unicode(K()) ))

And the result is like this:

'str'
u'unicode'

It is notable that str() converts unicode to str and unicode() converts str to unicode. No errors are raised if different string type is returned.

Now let's define other class:

# copied from https://github.com/benjaminp/six/blob/1.16.0/six.py

import sys
PY2 = sys.version_info[0] == 2
def python_2_unicode_compatible(klass):
    """
    A class decorator that defines __unicode__ and __str__ methods under Python 2.
    Under Python 3 it does nothing.

    To support Python 2 and 3 with a single code base, define a __str__ method
    returning text and apply this decorator to the class.
    """
    if PY2:
        if '__str__' not in klass.__dict__:
            raise ValueError("@python_2_unicode_compatible cannot be applied "
                             "to %s because it doesn't define __str__()." %
                             klass.__name__)
        klass.__unicode__ = klass.__str__
        klass.__str__ = lambda self: self.__unicode__().encode('utf-8')
    return klass

@python_2_unicode_compatible
class S(object):
    def __str__(self):
        return u'str'
    def __unicode__(self):
        return 'unicode'

print(repr( str(S()) ))
print(repr( unicode(S()) ))

And the result is like this:

'str'
u'str'

Now take a deeper look at python_2_unicode_compatible implementation, it is doing two things:

(checks if py2)
copy __str__ to __unicode__
set __str__ to unicode(self).encode('utf-8')

So (along with wrapping with python_2_unicode_compatible) the correct way to implement __str__ is to return u-string.

cf: https://wandbox.org/permlink/xHIO4C7HIk2J2kZL