Alas, Yakov is sort of wrong about nation-wide TV campaigns and their influence on Yandex's popularity. When campaigns launched, Yandex already was the top search engine and portal in Russia, beating its major rival Rambler by a noticeable amount of fame, traffic and search share.

Nation-wide campaigns on TV and outdoors, in subway, print and everywhere else (presence and sponsorship at events etc) pursue a main goal of growing awareness of people around the country, so that Yandex brand is known and "deeply sunk" in the mind of people, as it was (and to some degree stays true) for Yahoo in western markets, and it's what Google tries to take over. Ultimate goal of the whole marketing is to build an "Internet is Yandex" meme for layman people.

Google mostly failed in competition over main product – i.e Yandex is good enough for local search, that Google can't yet offer anything much superior to Yandex's search-based products that could be a flagship of marketing efforts and serve as a good reason for conversion or successful word of mouth marketing.

So Google's turning to advertising, which (assuming they plan creative campaigns and throw large enough lumps of money into plastering cities and sites with ads) gives them a chance of gaining a greater mindshare.

But that gain will happen not due to conversion of current user base, but rather by attracting new users, luring them with services that Google can be sure are top quality and which aren't overshadowed by equal Yandex or other local players' offerings. Probably that's why Google moved from marketing its search to promoting Earth/Maps and created Mail viral videoad.

Yes, Yandex is slowly losing its search share, and there're new traffic kings in Russian web (classmates.com's clone Odnoklassniki.ru and uber-portal Mail.ru), but it's still a big question what should Google do to just get close to its main competitor, which is still Yandex. Overthrowing an established and growing local brand is quite a task.

Yandex was known to Internet users and was a top player but it only became a BRAND nation-wide, for mass market, after TV campaign, that's for sure :)

People will only switch if Google offers something truly better than Yandex. If Google offers something that is just as good as, but not leaps better, then people won't switch, no matter how much advertising.

I've just checked and Google still does an extremely poor job with inflections, neither it can fix Russian spelling errors. I would not expect them gaining any market share in Russian-speaking world before they support Russian properly.

Yandex is the leading search engine in Russia leaving Google much behind them
This chart shows how many visitors visited Russian web site from different search engines
http://www.liveinternet.ru/stat/ru/searches.html?period=month
the blue line is Yandex
the green line is Google
Yandex is the leader!