is G smart enough to figure out that air tickets and hotel reservations are related?
I think Google have many sources of data to make this correlation.
First, the web structure. There are probably many hotel pages linking to air tickets pages, which creates a pattern (and analysing backlinks to these pages, the pattern becomes much more clear).
Next, everytime people make a search, they tell Google that there is a relation. Several people search for [tickets to Paris] and then [hotels in Paris] in a short time frame; Google are certainly taking notes.
And then, user behavior tells Google even more. People visit a hotels site, click to a air ticket site, and then browse several pages, stay long, bookmark, etc.
Now, give this load of information, accumulated over years, to the Army of statisticians which Google certainly have on staff, and they will probably find patterns to tell the relevant links from the irrelevant ones.
Compare this to, e.g., footer links in a jokes site pointing to a mortgage site. Few links exist on the web between jokes and mortgage sites (most are paid ones); few people click on such links; those who click, probably won't stay long; and searches for [jokes] and [mortgages] are in different circles.
Google can certainly tell the difference between these cases.