I dont see any red stuff on their site, but no matter...
The header logo will either be a JPG or GIF file in that template's images folder.
includes/templates/THAT-RED-TEMPLATE/images/logo.gif (or logo.jpg)
Just replace it with yours.
You can ensure pixellation is correct by ensuring the height given in the stylesheet for #logoWrapper (if applicable) corresponds with the pixel height of your new logo.
**includes/languages/english/header.php **
or
**includes/languages/english/THAT-RED-TEMPLATE/header.php **
... will contain important defines that reference the header logo (such as logo.gif - if you want logo.jpg, then that define needs changing...