Why do we assume that the first humans were dark-skinned?
The first modern humans evolved about 200.000 years ago in Africa. When they lost their body hair (or at least most of it), they needed some other protection of their skin from the sun - otherwise they are prone to develop melanoma. Melanin is such a protection, and the rate of melanoma is much lower in dark skinned people. 
There is also a nice correlation between latitude and skin color - the more to the north (and to some degree to the south as well) you get, the lighter the skin color of the population gets. The reason for this is likely the better ability to synthesize Vitamin D (for which you need sunlight on the skin):


The evolution of human skin coloration.
The evolution of human skin ans skin color.
Development of different human skin colors: a review highlighting
photobiological and photobiophysical aspects.
North-South gradients of melanomas and non-melanomas: A role of
vitamin D?


The lightening of the skin occurred after humans moved to Europe:


The Timing of Pigmentation Lightening in Europeans


And we even know, that this occured more than once, since the genetic reasons for lighter skins are different between europeans and light skinned asians.
A lot of this we know via sequence comparisions of genes involved in pigmentation, there you can trace mutations and see, where they show up first and how they migrate over time. One very good example is the melanocortin-1-receptor (MC1R), which is mutated pretty often in europeans (mutations in this gene are generally associated with lighter skin and hair color; people with red hair carry certain mutations in this gene) but its under selection pressure to not mutate in africa (there are almost no known mutations in MC1R for africans). Another example would be a mutation in the SLC24A5 gene, which is exclusively found in europeans, but not in asians and which accounts also for lighter skin. I stop here for the moment, if there are more specific question, go ahead.


The genetic architecture of normal variation in human pigmentation:
an evolutionary perspective and model
Genetic Variation at the MC1R Locus and the Time since Loss of Human
Body Hair
SLC24A5, a putative cation exchanger, affects pigmentation in
zebrafish and humans.