Google and Nokia announced a partnership to provide search function for Nokia phones at the Mobile World Congress in Barcelona on February 12th.
Therefore Google search will be available on Nokia N96, Nokia N76, Nokia 6210 Navigator and Nokia 6220 classic.
Nokia Search makes it possible for mobile users to search content on their device and use local search engines for a complete mobile experience.
Side Note: the Nokia N95 8GB was the first mobile device to fully support YouTube almost year ago. (always good to know that the Iphone is not the first and only one to support YouTube)