I am sure there is a very easy solution to this, but cannot seem to get this to work:

I have the following rule:

u: (search for _* on Google)
Searching for _0 on Google

The above normally works well, except for instances where the query contains the word “on”.

For example, the input “Search for man on the moon on Google” will not match, since the wildcard only consumes the word “man”.

I apologise if the solution is extremely trivial (which I think is the case), but cannot come up with a solution.

I don’t know that there are any “easy” solutions. But there are solutions.

Discard the trailing on google and resubmit input, noting for next time thru that you have done so.
1.  u: (_* on Google )  $$search = 1 input(‘_0) fail(SENTENCE)
    u: ($$search search for _0)

Similarly in spirit one could do (not tested) disabling the match code for the two words “on google”
  u: (* _"on Google”) unmark(* _0)
  u: (search for _*)

Grab the stuff as facts and discard a trailing on, and reconstitute.
2. u: (search for _* Google)
      Then you could burst the wildcard into word facts, check the last one to see if it has the word on, and if so delete it and then reconstitute the phrase without it.

Add a search that expects an extra “on”
3. u: (search for _* on _* on Google) 
    $$tmp = join (‘_0 _ on _ ‘_1 )
  as well as the normal one that doesn’t
  u: (search for _* on Google)

4. memorize the entire phrase after search for, do a substitution check for “on google” deleting it and using the result.
  u: (search for _*)
    $$tmp = substitute(character ‘_0 “on google” “”) 
  etc

The issue that you are raising, in general, has to do with how I chose to do pattern matching.  Efficiency is a major goal.
The matcher is not allowed to backup and try alternative bindings, as that would slow the system down enormously without being universally useful. It is, however, allowed to unbind once the first match it made, and try an alternative.  That mechanism is also exploitable by the RETRY command on output, which allows the rule to reexamine the same input, but starting from a later 1st match in it

So your pattern “search for * on google” fails because once “search” has been bound, if the pattern later fails, the only thing it is allowed to do is unbind that one and try to find a different “search” elsewhere in the sentence along with the rest of your pattern. If that fails, matching fails.  My revision of “* on google” would work because when it matches “on” initially within the input and then fails google, it is allowed to unbind that on and search for a later one.