Letterheads are stored as "Subforms" in your mail database. Mail then uses them on the memo form as a computed subform. The action that allows the user to choose one of the letterheads, adds their choice to an environment variable called "DefaultLogo."
To change the letterhead, you need to add the subform - then add the subform to the form "Letterheadchooser" so it can be selected. The changes do need to be applied accross the organization, otherwise if a recipient does not have the subform they will get an error message on opening your mail "Subform xxxx not found".
An easier way to create a custom Letterhead for you or your users is to create personal stationary instead. It will allow you to create a message and use it as much as you want. With this you get a rich text field at the top of the and bottom of your memo. This stationary template will reside in the drafts folder.