Indeed this behavior doesn't seem to be documented.

When the string is unicode and the fillchar non-unicode Python
implicitly tries to decode the fillchar (and possibly it raises a
TypeError if it's not in range(0,128)):
>>> u'x'.center(5, 'y') # unicode string, non-unicode (str) fillchar
u'yyxyy' # the fillchar is decoded


When the string is non-unicode it only accepts a non-unicode fillchar
(e.g. 'x'.center(5, 'y')) and it raises a TypeError if the fillchar is
unicode:
>>> 'x'.center(5, u'y') # non-unicode (str) string, unicode fillchar
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: center() argument 2 must be char, not unicode

If it tries to decode the fillchar when the string is unicode, it could
also try to encode the unicode fillchar (and possibly raise a TypeError)
when the string is non-unicode.

Py3, instead, seems to have the opposite behavior. It implicitly encodes
unicode fillchars into byte strings when the string is a byte string but
it doesn't decode a byte fillchar if the string is unicode:

>>> b'x'.center(5, 'y') # byte string, unicode fillchar
b'yyxyy' # the fillchar is encoded
>>> 'x'.center(5, b'y') # unicode string, byte fillchar
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: The fill character cannot be converted to Unicode

In the doc [1] there's written that "The methods on bytes and bytearray
objects don’t accept strings as their arguments, just as the methods on
strings don’t accept bytes as their arguments." so b'x'.center(5, 'y')
should probably raise an error on Py3 (I could open a new issue for this).

[1]:
http://docs.python.org/3.0/library/stdtypes.html#bytes-and-byte-array-methods
- In the note