$ py -c "from urllib import quote; print quote('тест')"
%D1%82%D0%B5%D1%81%D1%82
$ py -c "from urllib import quote; print quote(u'тест'.encode('utf-8'))"
%C3%91%C2%82%C3%90%C2%B5%C3%91%C2%81%C3%91%C2%82

$ locale
LANG=en_US.UTF-8
LC_CTYPE="ru_RU.UTF-8"
LC_NUMERIC="ru_RU.UTF-8"
LC_TIME="ru_RU.UTF-8"
LC_COLLATE="ru_RU.UTF-8"
LC_MONETARY="ru_RU.UTF-8"
LC_MESSAGES="ru_RU.UTF-8"
LC_PAPER="ru_RU.UTF-8"
LC_NAME="ru_RU.UTF-8"
LC_ADDRESS="ru_RU.UTF-8"
LC_TELEPHONE="ru_RU.UTF-8"
LC_MEASUREMENT="ru_RU.UTF-8"
LC_IDENTIFICATION="ru_RU.UTF-8"
LC_ALL=ru_RU.UTF-8

и в то же время

>>> from urllib import quote
>>> quote('тест')
'%D1%82%D0%B5%D1%81%D1%82'
>>> quote(u'тест'.encode('utf-8'))
'%D1%82%D0%B5%D1%81%D1%82'