If the letters were originally created using mailmerge, the simplest thing
would be to modify the mailmerge data main document by placing the necessary
information in the header and then re-execute the merge.

Otherwise, I would create a template with the necessary header information
in it and then use a modification of the code in the article the article
"Find & ReplaceAll on a batch of documents in the same folder" at:
http://word.mvps.org/FAQs/MacrosVBA/BatchFR.htm

to set a Range to the text in each letter, create a new document from the
template and then insert the Range into that document.

Post back if you need help with the VBA code.

Here is the code that you will need.  BEFORE RUNNING THE CODE, I would
suggest that you make a copy of all of the documents in another folder just
in case something goes wrong.

Dim myFile As String, PathToUse As String, SourceName As String
Dim Source As Document, Target As Document
'Modify the path in the following statement so that it points
'to the folder where the documents are located.
PathToUse = "C:\Test\"
'Close all open documents before beginning
Documents.Close SaveChanges:=wdPromptToSaveChanges
myFile = Dir$(PathToUse & "*.doc")
While myFile <> ""
   'Create a new document containing the header information.
   Set Target = Documents.Add("template with the header in it.dot")
   'Open document containing the text
   Set Source = Documents.Open(PathToUse & myFile)
   'Get the name of the document
   SourceName = Source.FullName
   'Set the text in the new document equal to the text in the source
document
   Target.Range.FormattedText = Source.Range.FormattedText
   'Close the source document
   Source.Close wdDoNotSaveChanges
   'Save the new document with the name of the source document
   Target.SaveAs SourceName
   'Next file in folder
   myFile = Dir$()
Wend

You could do this with a batch processing macro, provided all the documents
are in the same folder.

The following macro http://www.gmayor.com/installing_macro.htm  will replace
the existing header with whatever header you first save as an autotext entry
called 'logo'.

If you wish to *add* the company header to an existing header, the code will
require modification - and if some of the documents have multiple sections
you will have to add code to process those sections, but the basic code will
work for simple documents. Try it on a few copies in a folder created for
the purpose.

If you want more help with this I will not be around again this weekend. Ask
your further questions in the VBA newsgroup.

Sub AddAHeader()
Dim myFile As String
Dim PathToUse As String
Dim myDoc As Document

' Get the folder containing the files
' Save the header to insert as an autotext entry
' called 'logo'
With Dialogs(wdDialogCopyFile)
   If .Display <> 0 Then
       PathToUse = .Directory
   Else
       MsgBox "Cancelled by User"
       Exit Sub
   End If
End With

'Close any documents that may be open
If Documents.Count > 0 Then
   Documents.Close Savechanges:=wdPromptToSaveChanges
End If

If Left(PathToUse, 1) = Chr(34) Then
   PathToUse = Mid(PathToUse, 2, Len(PathToUse) - 2)
End If

myFile = Dir$(PathToUse & "*.doc")

While myFile <> ""

   'Open each file and make the replacement
   Set myDoc = Documents.Open(PathToUse & myFile)
   ActiveWindow.ActivePane.View.SeekView = wdSeekCurrentPageHeader
       Selection.WholeStory
   Selection.Delete Unit:=wdCharacter, Count:=1
   Selection.Style = ActiveDocument.Styles("Normal")
   NormalTemplate.AutoTextEntries("Logo").Insert Where:=Selection.Range, _
       RichText:=True
   ActiveWindow.ActivePane.View.SeekView = wdSeekMainDocument
   myDoc.Close Savechanges:=wdSaveChanges
   myFile = Dir$()
Wend

End Sub