Some viruses are encrypted so that the anti-virus can't identify them, but what I don't understand is: why wouldn't the anti-virus detect them, considering they have to decrypt themselves before running? Wouldn't the anti-virus understand the malicious code in that decryption step, before the virus could run?
There are a few ways malware could encrypt itself to thwart antivirus detection:
Derive a key from target specific information like hashes of known files, user names, and network shares. Check out Ars Technica's description of Gauss.
Encrypt itself with a random, but relatively short key. When the malware runs, it will have to brute force the key. Many AV sandboxes have a timeout on the amount of time a particular sample can run, if the brute force process takes longer than this timeout, the malicious payload won't be decrypted.
Retrieve the key from the internet. The attacker may host a web server with the key on it. They then could use timing, IP information, or client based parameters to determine if they key should be sent.
Of course, in order to run the encrypted payload, the malware must be decrypted. If it is decrypted, antivirus may detect it, but the malware may detect the AV first.
Finally, the mechanism of having an encrypted payload using host based, random, or network based keys may itself be used as a signature for malware. The AV may not know what the sample would have done, but it could prevent it from running in the first place.