Great, but that isn't actually a version
I assume you mean 4.1.9? If you could update that, that would be great.
As for changing colors, your best friend in the software is going to be webmaster mode. It tells you exactly which template is which. Once you determine what template something is in, you can open it up to see what classes it is calling, and then by looking at skin1.css, you can see how the color is called.
As for moving the search, you would simply move the include from one template to the other. THe include for the search function looks like this:
{include file="customer/search.tpl"}
Simply move that line of code from the header to the left hand menu, which is in customer/home.tpl.