Проблема Python urllib urlencode с æøå

Вы должны передать словарь в urlencode, а не строку. Смотрите правильный пример ниже:

from urllib import urlencode
print 'http://www.test.com/?' + urlencode({'q': 'testæøå'})

urlencode предназначен для использования словаря, например:

>>> q= u'\xe6\xf8\xe5' # u'æøå'
>>> params= {'q': q.encode('utf-8')}
>>> 'http://www.test.com/?'+urllib.urlencode(params)
'http://www.test.com/?q=%C3%A6%C3%B8%C3%A5'

Если вы просто хотите URL-кодировать одну строку, вам нужна функция quote:

>>> 'http://www.test.com/?q='+urllib.quote(q.encode('utf-8'))
'http://www.test.com/?q=%C3%A6%C3%B8%C3%A5'

Я предполагаю, что UTF-8 - правильная кодировка (так и должно быть для современных сайтов). Если то, что вы на самом деле хотите ?q=%E6%F8%E5, то кодировка, которую вы хотите, вероятно, будет cp1252 (аналогично iso-8859-1).