The problem is described as the customer answering basically 5 different criteria (age range, gender, interests, category, price range) about the gift recipient, and the computer returns a list of 10 gifts.

Based on the description of the problem being solved, I'd guess they would have used "FARGO", a sort of report generation language, which probably had some predefined way to "AND" those criteria together and print out 10 matches. FARGO may have morphed into RPG by 1962, but the idea would have been similar.

http://bitsavers.org/pdf/ibm/1401/C24-1464-3_1401_fargo.pdf

Unfortunately no source code. I've thought about how this might be implemented. The video says there are 3000 items; the IBM 1401 only has 4000 characters of memory (unless it has the 12,000 character expansion memory box, which I didn't see in the video). So most of the data must be on magnetic tape. At 15000 characters per second, ten seconds of processing would permit 50 characters per item, which seems reasonable.

So my theory is that the program runs through the 3000 records on tape and matches (ranks) them against the customer's input. It could keep track of the current top 10 matches as it goes through. Then it can print them out at the end. (I'd expect some pseudo-randomness so customers don't get the same results.)

Of course, they could do something simple, such as having a small number of pre-computed lists and just print one based on the customer's input.