A paper from the Federal Aviation Administration appears to be the first rigorous examination of the pesky phenomenon of jet lag. It's titled Time-Zone Effects on the Long-Distance Air Traveler, and is remarkably readable for its genre. It tells us quite confidently that the first recorded instance was in the 1930s.
Circadian rhythms became a matter of importance to travelers with the evolution of the airplane and the feasibility of long-distance flights. Wiley Post, the record-setting global flier of the 1930's, was the first to recognize the adverse effects of time-zone displacement on the sleeping and eating cycles of air travelers. Prior to his 8-day global flight of 1931 and his 7-day solo global flight of 1933, Post determined the effects of altered sleep-wake cycles on his flying proficiency. He also experimented with an irregular schedule of meals and worked out a conditioning program designed to break his habitual sleeping and eating patterns. As indicated in his book, Post felt that the time-zone effects were significant and that the steps he took to adjust to them were beneficial.
The next published discussion of time-zone effects in global flying is a 1952 report by Strughold. Since then, and especially since jet-powered air transports were introduced in the late 1950's, the literature on aerospace medicine has contained many papers on "jet age" time-zone effects. Crew members and passengers have repeatedly reported adverse physiological and psychological consequences of rapid long-distance flights-of east-to-west or west-to-east flights in particular.
The report cites Post's 1935 book, Around the World in Eight Days, though I've been unable to find an online version to quote the original recounting. But it seems to be the earliest recorded instance.