See the blank white vertical space on the left of their search result page? Wouldn’t a vertical skyscraper banner fit nicely here? I don’t think keyword-based ads would make sense in news (as opposed to web and Usenet searches) but I don’t expect Google to have gone philanthropic. There’s always the "premium sponsorship" horizontal "text banners" but I don’t see any right now.
Where else is the money? Publishers? Did anyone in the 4,000 sites Google currently queries pay for it? I don’t think so. Intranet portals? Then Google would soup up its current offering and compete with Moreover and Factiva. Not impossible, though Google’s 100% automatic approach make it hard to guarantee the quality level they provide.
Update: Google launching search site for news: "Google is initially offering the news service for free, without any advertising support. It said it plans to see what kind of demand the site generates before it considers possible ways to make money from it." Yeah, right, like they didn’t plan their business model before even allocating money to this service.
10/04/02 update: [Phil Wolff] Premium Google News.