How to convert a string from CP-1251 to UTF-8?

Your string d is a Unicode string, not a UTF-8-encoded string! So you can't decode() it, you must encode() it to UTF-8 or whatever encoding you need.

>>> d = u'\xc1\xe5\xeb\xe0\xff \xff\xe1\xeb\xfb\xed\xff \xe3\xf0\xee\xec\xf3'
>>> d
u'\xc1\xe5\xeb\xe0\xff \xff\xe1\xeb\xfb\xed\xff \xe3\xf0\xee\xec\xf3'
>>> print d
Áåëàÿ ÿáëûíÿ ãðîìó
>>> a.encode("utf-8")
'\xc3\x81\xc3\xa5\xc3\xab\xc3\xa0\xc3\xbf \xc3\xbf\xc3\xa1\xc3\xab\xc3\xbb\xc3\xad\xc3\xbf \xc3\xa3\xc3\xb0\xc3\xae\xc3\xac\xc3\xb3'

(which is something you'd do at the very end of all processing when you need to save it as a UTF-8 encoded file, for example).

If your input is in a different encoding, it's the other way around:

>>> d = "Schoßhündchen"                 # native encoding: cp850
>>> d = "Schoßhündchen".decode("cp850") # decode from Windows codepage
>>> d                                   # into a Unicode string (now work with this!)
u'Scho\xdfh\xfcndchen'
>>> print d                             # it displays correctly if your shell knows the glyphs
Schoßhündchen
>>> d.encode("utf-8")                   # before output, convert to UTF-8
'Scho\xc3\x9fh\xc3\xbcndchen'