Muttprint formats the printing of Mutt and other mail clients to be as pretty as the printing of Mozilla or Kmail.
It can print a little penguin -- or the Debian logo -- on the first page (suitable pictures can be found in the ospics package) and a headline on every page. Furthermore, it only prints the most important headers, but not the whole plethora of them. Finally, it can even print two pages on one page in landscape format.