A polymorphic virus is a particular type of computer virus that changes or 'mutates' as it spreads.
Many years ago, most anti-virus (AV) software worked simply by scanning through files, the boot sector, memory, etcetera, for the 'signature' of the virus - the sequence of bytes that made up it's instructions. Polymorphic viruses1 hoped to defeat this by changing their signature regularly, normally on infection of a new host.
There are two main methods used in making a virus polymorphic. The first (and simplest) was simply to encrypt the body of the virus using (very) weak encryption, using a different key each time. Variations on the theme include using randomly chosen mechanisms with randomly chosen keys. These are more accurately known as 'encrypting' viruses.
These are defeated by the latest AV programs because the decryption code must necessarily be outside of the encrypted contents of the virus itself. The virus' decryption routines became the signatures which the AV software scans for.
The other type of polymorphic virus is far trickier to write. They are written using self-modifying code and perform such tricks as moving various blocks of code around - which affects the execution order for various operations (scan, infect, activate, etc.), but does not change the overall effect of the code.
Other tricks include things like inserting No OPeration codes, or scattering the code over several address blocks and randomly jumping around memory. These tricks have made virus detection a lot more difficult and complicated than it once was, and increases the risk of finding false positives.
Today, most cutting-edge virus design is done for AV companies in R&D labs. Polymorphism is usually utilised in conjunction with other techniques such as stealth, armouring, and multipartite vectors of infection.
1: virii = 30,100 hits, viruses = 818,000 on google.
Sources:
http://www.pakcert.com.pk/pages/Polymorphic_Virus.htm
http://vil.nai.com/vil/virusSummary.asp?virus_k=458
http://www.ladysharrow.ndirect.co.uk/Virus%20Information/polymorphics_1993.htm
http://www.research.ibm.com/antivirus/timeline.htm