Уже не помню

Но у меня заработало вот так:

var ref = location.href; // document.referrer;
function getQ(str) {
	var qStr = /[\?&](?:text|q|words|query|search)=([^\?&]*)/.test(ref);
	return qStr && decodeURI(RegExp.$1);
}
alert(getQ(ref));

Проверял через запуск из адресной строки:

javascript: (function() { var ref = location.href; function getQ(str) { var qStr = /[\?&](?:text|q|words|query|search)=([^\?&]*)/.test(ref); return qStr && decodeURI(RegExp.$1); } alert(getQ(ref)); })();

Особо развлекаться было лениво... В общем, в Firefox 2.0+, Opera 9.2+ и IE 6.0, 7.0 все Ok.

К тому же, проблема может быть из-за (кривого) блокирования referer'ов каким-нибудь файрволом. У меня вот они вообще подменяются.

[UPD]
А вот с cp1251 – как-то сразу не обратил внимания – действительно траблы...

[UPD – 2]

Полагаю, можно сделать

unescape(qStr)

Потом попытаться перекодировать. Где в результате будет содержаться кириллица

/[а-яё]/i.test(qStr)

, то и использовать. Иначе – брать исходный unescape(qStr).