Address = to deal with?

Yes I guess so, but in particular the quest is 'inbuilt' as "to find information".

In the Uk we say "the police are on the trail of the criminal" for example.

It signifies a search to find something, in the case of your example, probably the New York Times seeking info. on the trade deficit problem.

I think that, in this case, "on the trail" is using a hunting analogy - ie it is as though the Times is following the trail of a hunted animal. Hunters would use an animal's scent, or clues like paw or hoofprints, broken branches etc to track it down. As with a hunted human. here is a dictionary definition of this meaning of trail: ". the track, scent, or the like, left by an animal, person, or thing, esp. as followed by a hunter, hound, or other pursuer."

Times in quest of - or in the quest for - would be better expressions.

On the trail can also mean that one is on a journey.

Address does more or less mean "to deal with" in this sense.