It seems that my suspicions, Brad B and the docs are right, you cannot alter the default notification template. It has to be overridden. Therefore the solution to the question I posed (for those who come across this) is as follows.
First, I'd recommend you make the logo you want to include a public document in your salesforce org. This is best approached by clicking the "Documents" tab (which may be hidden under the tab + sign).
From there upload your logo file, to the Shared Documents folder, making it an Externally Available Image
..then select and upload your file.
Putting this logo at the top of an e-mail can be done by creating a rich letterheaded e-mail, so click through Setup > Communication Templates > Letterheads click "New Letterhead" give it a name and label, make it "Available for use" and click to Save. In the letterhead editor, click "Select Logo" and then find your document in the popup.
Save your letterhead.
Now navigate to e-mail templates, Setup > Communication Templates > Email Templates and click to create a new one. Select "HTML (using Letterhead)" and click next,
Fill in your folder, template name and pick your letterhead from the dropdown. Choose freeform letter (for the best approval process looking email) make sure it is available for use and "Next".
Now you can set a subject and body as follows:
(to mimic default behaviour) )
With "Approval by email reply" enabled :
For the subject use Salesforce record awaiting approval
For the body:
{!User.FirstName} {!User.LastName} has requested your approval for
the following item.
To approve or reject this item, reply to this email with
the word APPROVE, APPROVED, YES, REJECT, REJECTED, or NO
in the first line of the email message, or click this link:
{!ApprovalRequest.External_URL}
If replying via email you can also add comments on the
second line. The comments will be stored with the approval
request in Salesforce CRM.
Note: For salesforce.com to process your response the word
APPROVE, APPROVED, YES, REJECT, REJECTED, or NO must be in
the very first line of the reply email. Also, any comment
must be in the second line.
If you do not have the approve by e-mail feature on, use:
Subject: Approval Request
Body
{!User.FirstName} {!User.LastName} has requested your approval for the following item: {!ApprovalRequest.External_URL}
Please click this link to approve or reject this record.
Thank you,
salesforce.com
Paste the same text into the plain text body field too, this means if users mail clients don't support rich content, they still get the message body.
Then, you have your duplicate e-mail template set up, but with a logo.
To assign this to an approval process, through the browser navigate to the approval process in question and click on the "Edit" downarrow at the top, and choose notification template:
On this page, you can select your e-mail template (using the lookup dialogue) and, once saved, next time the record approval e-mail is dispatched, it will have a logo on it!!
(regarding updating all Approval processes to use this new template en masse, I can't advise right now. You will have to update each one through the browser).
Best Answer
You can use a solution like Litmus to get a snappy and repeatable handle on all the different email clients.
Then ask your nearest HTML email expert to sanity-check the styles (and/or resets) and markup you're using to generate the email. Some elements work really consistently (tables) and others don't (typography).
Getting complex HTML emails to display consistently across clients will be a world of hurt for someone who doesn't do it for a living :-( try not to rely upon pixel perfection if at all possible.