How do I add a link "Advanced Search" next to the OOTB search (top area where I see the title of the site, etc.)
I am not sure of the process for editing the delegate control the implements the SearchBoxEx control. Your control is provided by an xml document in the OSearchBasicFeature. The file can be found in your [12or14hive]\TEMPLATE\FEATURES\OSearchBasicFeature\SearchArea.xml
This article talks about overriding that.
To edit the standard search webpart: