First, find the following strand in Nicola's code:

Code:

 

$('#submenu').prepend(

Then, at the end, before the  ');  of the "BEFORE / AFTER links" codes, or the  </span>');  in the "Left of Submenu" code,
add the following:

Code:

 

<form method="link" action="' + main_url + 'search/"><button type="submit">Advanced</button></form>

This will add a new button (to the right of the Go button), that'll link to the Search page.

Next, before the last 2 lines of the code:

Code:

 

//]]>
</script>

Add this:

Code:

 

$("div#submenu a:contains('Search')").remove();

This will remove the old Search link.