Python 3

In Python 3, the urllib package has been broken into smaller components. You'll use urllib.parse.quote_plus (note the parse child module)

import urllib.parse
safe_string = urllib.parse.quote_plus(...)

Python 2

What you're looking for is urllib.quote_plus:

safe_string = urllib.quote_plus('string_of_characters_like_these:$#@=?%^Q^$')

#Value: 'string_of_characters_like_these%3A%24%23%40%3D%3F%25%5EQ%5E%24'

From the Python 3 documentation:

urllib.parse.quote(string, safe='/', encoding=None, errors=None)

Replace special characters in string using the %xx escape. Letters, digits, and the characters '_.-~' are never quoted. By default, this function is intended for quoting the path section of a URL. The optional safe parameter specifies additional ASCII characters that should not be quoted — its default value is '/'.

That means passing '' for safe will solve your first issue:

>>> import urllib.parse
>>> urllib.parse.quote('/test')
'/test'
>>> urllib.parse.quote('/test', safe='')
'%2Ftest'

(The function quote was moved from urllib to urllib.parse in Python 3.)

By the way, have a look at urlencode.

About the second issue, there was a bug report about it and it was fixed in Python 3.

For Python 2, you can work around it by encoding as UTF-8 like this:

>>> query = urllib.quote(u"Müller".encode('utf8'))
>>> print urllib.unquote(query).decode('utf8')
Müller