/Applications/Mail.app/Contents/Resources/English.lproj/Compose.stringsWhen I tried to edit this in the terminal, all I got was gibberish - it's a Unicode text file. Opening and saving it in the GUI works fine; you just have to use a control-click on mail.app to "Show Package Contents" in a new Finder window, and specify which application to open it with (I used TextEdit).
Amazingly enough, the text file is even commented, explaining what each line does. You'll have to do some work to change the default reply string ("On March 23, robg wrote..."), as the date format strings are all variables - I imagine they match those used by the system date command, which you can view in the man pages:
man strftimeHave fun customizing, but you should probably make a backup copy of the unmodified file first -- just in case! Any changes made take effect on the next launch of mail.app.
This tip was posted to the X4U mailing list by a member of Apple's mail team.
Panther update: As noted in the comment below, you now need to edit /System -> Library -> Framework -> Message.framework -> Resources -> English.lproj -> Message.strings. In addition, you'll have to reboot after making the change to see it take effect.

