Well, uvesten is correct in saying that potatoes are flowering plants and as such they can reproduce sexually. However, as everyone mentions potatoes can, like many plants, reproduce asexually by putting out clones.
Since clones are (by definition) genetically identical to the parent plant, this would seem to rule out the possibility of producing different varieties (or even species) from clonal propagation.
But! this very interesting study by Jiang et al. looked at Arabidopsis lineages (Brassica family). They found:
"in vitro regeneration of Arabidopsis plants results in a high frequency of heritable phenotypic variation "
That is, regenerant Arabidopsis plant lineages displayed extensive phenotypic somaclonal variation - the cloned "offspring" were not genetically identical. They attributed most of this genetic variation to an increased base substitution frequency in the regenerant offspring but there may also be unknown epigentic factors as well.
Jiang et al. summarise:
... somatic mutation rates are characteristically higher than germline rates in multicellular organisms  and has important particular potential consequences for the evolution of plants, given that they frequently adopt life cycle strategies that involve regeneration from somatic tissues.
So, perhaps some of the variation we see in plant species which commonly propagate asexually actually arose during this process and not via sexual reproduction ... ? This would be good news for houseplants which are nearly always propagated asexually.
However, I am not sure whether this extends to potatoes.
Jiang et al. 2011, Current Biology, 21, 1385, Regenerant Arabidopsis Lineages Display a Distinct Genome-Wide Spectrum of Mutations Conferring Variant Phenotypes