In den meisten Themes befindet sich das Logo, wie du schon richtig erkannt hast im header. (header.php). Meisten links oben, weil das Auge meistens dort immer als erstes Bilder wahr nimmt. Im header.php wird auf das Logo verlinkt sprich < a href. . . . > Im Code brauchst du nichts verändern. Das einzige was du verändern musst ist? Richtig, das Logo. Also gehst du in den Ordner von deinem Template, der Bilder einschließlich das Logo beinhaltet. Öffnest das Bild mit einem Grafikprogramm, wie z.B Photoshop oder die kostenlose Alternative GIMP. Dort bearbeitest du das Logo speicherst es nur und voilá.
Hochladen, ggf. Cache löschen, fertig.