Part of the game in writing patents is that you start with a very broad claim (like the one quoted in the article), and then add a number of so-called "dependent claims" that add more details. This technique allows you to have it both ways as the patent-holder: it's very hard for the defendant to say out of hand that the patent doesn't apply (because the first claim is so broad), but it's also hard for them to knock it down with an obvious bit of prior art (because the dependent claims are so specific.)
In this case, a lot of the dependent claims still look pretty laughably obvious and the old Palm OS may be prior art for them. (I never used one, so I don't really know.) But does it include "the steps of determining a context for the input of the information identifier, and varying [the] ranking [of modules to query] in accordance with the determined context" (claim 8)? Did it before 2000 have one of the heuristics "locate Internet web pages" (claim 15)? Android does. And even though the statute and every policy rationale for patents require that the claimed invention be non-obvious (unlike these), it's been hard to get that requirement applied seriously.
I certainly wish Google's litigators the best of luck in finding prior art and winning their case. This kind of patent hurts everyone who wants to actually innovate and make things.