Last weekend I read a nice conversation in the #metasploit IRC channel. A user wanted to know how to bypass antivirus signatures and somebody pointed out to a presentation made by the Offensive-Security guys in Schmoocon, back in 2008.
In a nutshell, we have to patch the binary with a Hex editor. The original binary will be 'Xored' to avoid the AV signatures and also a new routine will be added at end of the DATA section to decode the contents of the binary in run-time.
You can find a copy of the video here