tl;dr: The nature of the way fares have been set up here happens to make it hard to search for JQ with an overnight stop in CNS, and some of these possibilities will be missed. Using the multicity search forces the pricing engine to consider going via CNS instead of other routes. Matrix finds it without a hint because it is better.

JetStar has fares filed on the Sydney–Osaka market, but none of them are valid for connecting itineraries. This complicates the search.

My speculation is that JQ has done themselves no favours in the structure of the fares they have published.

I took a look at the public fare tariff that JetStar (JQ) has published on the Sydney-Osaka market.

Each fare on this market that JQ has published contains the following restriction in the "Flight Applications" category.

FLIGHT APPLICATION  
   THE FARE COMPONENT MUST BE
   ON DIRECT FLIGHTS.

Just to be sure, the same restriction is repeated in the "Transfers" category.

TRANSFERS   
   TRANSFERS NOT PERMITTED.

This means that you cannot use any single JQ fare on SYD-OSA to build your desired itinerary. Instead we have to go down a more complicated route of using multiple fares.

Pricing itineraries with multiple legs using a single through-fare.

Usually when a flight search engine begins searching, it will start by looking at the fare tariffs that are published on the market the traveller desires. In this case, your market is SYDOSA, that is, Sydney (SYD) to Osaka (OSA).

Now it is computationally quite easy to sort these fares by price, and then, from lowest to highest fare, for each fare, try to find some set of flights between the origin and destination on which that fare is valid. Each flight set has some taxes and fees associated with it which must be added to the cost of the fare, and from there, the set is then be ranked by some suitability factors (for instance, total time of travel). Finally, some small subset of this enormous number of options is ready to present to the user.

Pricing an itinerary by combining multiple fares.

But that doesn't work for the JQ fares.

An alternative approach is needed. We split your itinerary in two halves. We look first for valid fares between SYD and some intermediate connecting point, then we look for fares between the connecting point and OSA, and then we repeat the exercise given above for those two halves of the itinerary. Then we have to check whether the fares in question allow themselves to be combined together. Finally we need the actual connecting flights to be reasonable. Then we repeat this for all the candidate connecting cities. (Each pair has its own list of candidates, we won't be considering SYD-AMS-KIX, for example.)

We can also repeat the above, covering the itinerary with three or four fares, or more, usually at most sixteen.

This is hard work. You can't just pick up any two random fares and glue them together. Just to illustrate, the JQ fares on SYD-CNS have the following restrictions in relation to combinations.

COMBINATIONS    
  END-ON-END
     END-ON-END COMBINATIONS PERMITTED WITH DOMESTIC/
     INTERNATIONAL FARES. VALIDATE ALL FARE COMPONENTS.
     SIDE TRIPS PERMITTED WITH NO RESTRICTIONS. FARES
     MUST BE SHOWN SEPARATELY ON THE TICKET. TRAVEL MUST
     BE VIA THE POINT OF COMBINATION.
     PROVIDED -
       COMBINATIONS ARE FOR CARRIER 3K/4M/9W/AA/AC/AF
       OR FOR CARRIER AY/AZ/BA/BL/CX/CZ
       OR FOR CARRIER DL/EK/ET/EY/FJ/FM
       OR FOR CARRIER GK/JL/JQ/KL/HX/LO
       OR FOR CARRIER LA/LH/LP/LX/LY/MH
       OR FOR CARRIER MU/NF/PX/QR/QF/QV
       COMBINATIONS ARE FOR CARRIER RJ/SB/TN/TK/UA/UL
       OR FOR CARRIER VN/XL/AI/JJ/DE
       OR FOR CARRIER KA/LJ/MK.
   OPEN JAWS/ROUND TRIPS/CIRCLE TRIPS
     FARES MAY BE COMBINED ON A HALF ROUND TRIP BASIS
     -TO FORM SINGLE OR DOUBLE OPEN JAWS/ROUND TRIPS/
      CIRCLE TRIPS.
     PROVIDED -
       COMBINATIONS ARE WITH ANY FARE FOR CARRIER 3K/4M/
       9W/AA/AC/AF
       OR FOR CARRIER AY/AZ/BA/BL/CX/CZ
       OR FOR CARRIER DL/EK/ET/EY/FJ/FM
       OR FOR CARRIER GK/JL/JQ/KL/HX/LO
       OR FOR CARRIER LA/LH/LP/LX/LY/MH
       OR FOR CARRIER MU/NF/PX/QR/QF/QV
       COMBINATIONS ARE WITH ANY FARE FOR CARRIER RJ/SB/
       TN/TK/UA/UL
       OR FOR CARRIER VN/XL/AI/JJ/DE
       OR FOR CARRIER KA/LJ/MK IN ANY RULE AND TARIFF.

Every fare on the whole ticket needs to be happy with these combinations.

(This is why we have the rise of "hacker fares", which is when we use several fares on several different tickets. When different tickets are involved, the combination restrictions don't apply.)

Why can't typical flight searches find this, even when you are specific?

Usually the result set is calculated in advance, and then the filters on the web page simply exclude certain results. If the engine did not discover what you wanted in the first pass, changing the filters does not fix that.

Why does the ITA Matrix have no difficulty with this?

Simply put, ITA Software is far and away the best at solving flight pricing problems. However, even Matrix struggles at times and there is still much value in understanding what is going on.

Why does the multicity search find it?

Using a multicity search does two things.

First, it forces the engine to consider the city you stop at. That dramatically changes the shape of the search. Itineraries on SYD-KUL-KIX cannot be considered anymore, and no time will be spent on them. That time is now dedicated to SYD-CNS-KIX.

Second, and perhaps more importantly here, some flight engines will consider the stopping city almost as a "hint" as to where a fare break point should be. The fare break point is the point between one fare and the next, so for a SYDCNS fare end-on-end with a CNSOSA fare, the break point is at CNS, whether or not you actually take a stopover there.

Now technically, there is no reason why a fare break need coincide with an actual stopover, because you can have a through-fare that permit stopovers midway through the fare. Nonetheless, I have found the multicity search is an invaluable way to communicate to the engine the fare break points it should investigate.

 On your specific questions.

Do flight searches assume that an option that has a long layover is always inferior to one with a shorter but sufficient layover?

Generally, yes, at fixed price; unless you specify otherwise.

Is Jetstar somehow reluctant to advertise alternative options for flying from Sydney to Osaka, either because it wants to flog 6am Sydney flights, or because it doesn't want to provide overnight accommodation for people in Cairns on a Saturday night?

If JQ wanted to discourage selling this route, they have a myriad of ways available to them to increase the price, and that would affect all sales channels (or whichever specific sales channels they wished). JQ could also totally disallow the combination that Matrix and multicity search finds by stipulating as much in the fare rules.

What can I do to find this option, and other competing options using either Cairns or any other airport, without already knowing that it exists?

Keep playing, keep learning. Air fare pricing is complex and full of nuances, idiosyncrasies and subtleties.

Look at each of the connecting cities specifically. Find out who flies what routes and on what schedules. Then you can focus on what you want more narrowly and give the pricing engine more of a chance to find what you want. Learn to read fare rules and ideally obtain access to the fare tariffs through a tool like ExpertFlyer or KVS.