There are two recent reviews about viral origins and contributions to life on earth at the open-source journal Genome Biology here and at Nature here . As parasites, modern viruses have evolved strategies for incredible levels of compaction, but this means their very compressed genomes do not leave a lot of evidence of their origin. There has been a huge amount of progress on this problem as more and more viruses get sequenced and especially with the discovery of "giant viruses" such as mimivirus. Genomic methods are being used to discover viruses literally everywhere, many of which contain previously unknown genomic sequences.
With the new evidence and new ideas, it looks possible that viruses evolved from a very ancient, independent branch on the tree of life. But here's where the story gets pretty wild- perhaps viruses, sporting the first DNA in order to evade RNA defenses, actually made the very first nucleus. In this case there's a little bit of virus in all of us.
The Nature article highlights that viruses in the present-day world grab sequences from their hosts and each other. This mixing of genetic information itself can shuffle genes between viruses and even animals, meaning that genes are in effect pooled across an entire population:
"When you look at a group of viruses, such as the algal viruses, there seems to be a very, very small core of conserved genes," says Curtis Suttle, a microbiologist at the University of British Columbia in Vancouver, Canada. "The rest is almost like a super-organism — a massive pool of genetic information that's being shared among all these different viruses." (from the Nature review).
Wow, the borg is here!
UPDATE: And we are the borg- a nice writeup from a few weeks back by Dan Vergano at USA Today about how humans and the bacteria in their gut together make a superorganism. Something just made me think of Taco Bell.