I'm by no means an expert in the field, merely a curious visitor, but I've been thinking about this and Google isn't of much help. Do we know of any lifeforms that don't have the conventional double-helix DNA as we know it? Have any serious alternatives been theorized?
To follow up what mbq said, there have been a number of "origin of life" studies which suggest that RNA was a precursor to DNA, the so-called "RNA world" (1). Since RNA can carry out both roles which DNA and proteins perform today. Further speculations suggest things like a Peptide-Nucleic Acids "PNA" may have preceded RNA and so on.
Catalytic molecules and genetic molecules are generally required to have different features. For example, catalytic molecules should be able to fold and have many building blocks (for catalytic action), whereas genetic molecules should not fold (for template synthesis) and have few building blocks (for high copy fidelity). This puts a lot of demands on one molecule. Also, catalytic biopolymers can (potentially) catalyse their own destruction.
RNA seems to be able to balance these demands, but then the difficulty is in making RNA prebiotically - so far his has not been achieved. This has lead to interest in "metabolism first" models where early life has no genetic biopolymer and somehow gives rise to genetic inheritance. However, so far this seems to have been little explored and largely unsuccessful (2).
I just saw this popular article in New Scientist which also discusses TNA (Threose nucleic acid) and gives some background reading for PNA, GNA (Glycol nucleic acid) and ANA (amyloid nucleic acid).
There has been a recent report on Science, which had much return in the general press, in which a bacteria was identified that could live in an environment where arsenic was subsituted to phosphorus (one of the components of DNA, forming the backbone of the double helyx).
This is the original paper:
A Bacterium That Can Grow by Using Arsenic Instead of Phosphorus
and the commentary appeared on Nature
Arsenic-eating microbe may redefine chemistry of life
There is, however, much critique on the methodology used in the paper, and on whether arsenic would really be incorporated in DNA instead of phosphorus.
Other than that... well if you consider virus as life-forms, there's plenty that do not have double stranded DNA, but have instead single strand DNA or single strand RNA or double strand RNA.
There are serious speculations that the origins of life were using RNAs both as enzymes and genetic information carrier.
Later this informative RNAs evolved into a more stable and less reactive DNAs, enzymatic role was delegated to proteins and RNA only remained into most crucial parts of expression chain (mRNA and rybosome) and some regulation mechanisms.
This recent Cell paper mentions a ribozyme (RNA enzyme) that ligates two oligonucleotides into itself. Given a sufficient source of input oligonucleotides and the correct conditions, it can catalyse its own replication and undergo Darwinian evolution, and can be thought of as a rudimentary form of RNA-based life.
The authors hypothesise that ligase-based RNA replicators could have been the first RNA replicators, which were later replaced by the now-standard polymerisation:
A somewhat different approach relies on RNA enzymes with RNA-templated RNA ligase activity to join oligonucleotide substrates to form complementary RNA products. It has been proposed that the first replicating, evolving systems on Earth operated by this mechanism and only later came to depend upon residue-by-residue polymerization
It should be noted that RNA ribozyme polymerases already exist, but many of them require proteins in addition to the RNA structure.