I'm not sure that coppermine or gallery have a threads integration available; they at least didn't when I looked some time ago...
It's easy to add a link to the ubb header, it's in the header.tpl file, just look for the string "profile" and it should be in there around that instance.
I use custom islands for everything, you can see an example at a client site
here all done using custom islands and CSS (modding files to use the custom islands though).
Well, there are some styles here at UBBCentral and several people have some on their sites (I have a list of paid styles at my homepage in my signature).
To submit items to google you could create a sitemap and feed links to google, yahoo, and bing; I have a paid mod (again at my homepage) called UBB.Sitemaps that does this automatically.
That header doesn't seem like it'd be too difficult to make, it'd likely take some time however to get everything to look right...
