If you look closely at the following design, you will notice that all of the details of the header are clearly marked out from the previous wireframe example. All I have done here is taken the wireframe and filled it with the most common elements that belong to all Moodle themes. I have then filled in the block areas with the colors that I want to use, and finally I made the left and right sideblocks a little prettier. For now, the most important area is the header, as this is what you will be concentrating on first.
It's basic but functional and doesn't require too much Photoshop manipulation. In actual fact, the only parts that really need Photoshop are the logo and block headers, but for the sake of having something to compare against while you create your own theme, it would be best if you build this design in Photoshop beforehand. If you do not have Photoshop, then any other...