From what I found out in legal correspondence and deeds, it appears that "will" is used far more often than "testament". Is one more formal than the other? If not, what is the difference between the two?
The full name of the document is Last Will and Testament. One definition:
A document in which a person specifies the method to be applied in the management and distribution of his estate after his death.
Will is a common term to refer to this document. I wouldn't call it informal; I think it's what people use most of the time. In a legal context you're probably better off using the full name, though.
Many legal terms use a pair of synonyms, one of Germanic origin, the other of Latin origin. This dates back to the Middle Ages, when a majority of the English population used Old English but many educated people (such as lawyers) spoke Old French or Latin. This developed into a habit of using such pairs even after the original motivation of expressing the same concept in two languages was lost. Such pairs are called legal doublets.
Examples: aid and abet, cease and desist, kind and nature, will and testament, …
Will (in this sense) and testament are synonyms. They can be used interchangeably (at least in normal speech, and I'm not aware of any legal difference). Will (the Germanic term) is a lot more common than testament (the French term).
These days there is no distinction, but traditionally wills dealt with real estate, while testaments handled personal estate. See, for example, this page from the University of Nottingham.