Why did humans lose their fur?
This is an interesting question, and there are a number hypotheses available to explain this phenomenon. The short answer (as far as I can say after my literature search) is that we don't know the answer for sure. The long version follows below.

The main problem with all these hypotheses is that though they may have a valid point, a definitive hypothesis hasn't been demonstrated yet. All these hypotheses are listed in the first reference, with a ton of additional references in the paper. I will summarize the different hypotheses only briefly here; for details please read the paper. The second reference is also interesting.

The point when this process started was after the last common ancestor of chimpanzee and humans when our two lines diverged. Chimpanzees are our closest relatives and still have hair coats, so this process must have started afterwards. Analyses of MC1R mutations (which affect pigmentation) suggest that human have been hairless for at least 1.2 million years. See reference 3 for details on this.

Aquatic ape hypothesis (also known as aquatic ape theory): This hypothesis states that modern humans spent some time semi-aquatic. In this lifestyle fur does not insulate very well and this led to an evolutionary disadvantage. 

Cooling hypothesis: This hypothesis states that the modern humans lost their hair when they left the forests and started to live on the savannah. There they got too warm with their fur and finally lost it. This hypothesis sounds logical at first thought, but has a few problems. Naked humans have two problems: during the day they collect quite some heat via their skin, which requires them to have a cooling system (we sweat to cool us), and during cold nights we need a lot of internal energy to keep our temperature stable. Insulation however works both ways (not only keeps the warmth in, but also can keep heat out), and indeed some savannah monkeys have denser fur than their relatives in the forest. The cooling system will also lead to water loss and potential dehydration.

Hunting hypothesis: This hypothesis states that humans started becoming carnivores and therefore had the need to run for extended periods of time to hunt for meat. This leads to thermal overload; without a fur they can release this heat much faster to avoid overheating.

Bipedality hypothesis: This hypothesis assumes that modern humans, walking on two feet, have a lower direct influx of solar radiation. This lowers the chance for overheating.

Allometry hypothesis: Allometry states that species which get bigger during evolution, do not have all their organs getting bigger at the same rate. The hypothesis states that humans got bigger, the number of hairs stayed the same, and finally got lost.

Clothing hypothesis: One of the more illogical hypotheses, this assumes that hair loss wasn't critical for humans as they managed to make themselves clothes.

Vestiary hypothesis: A mix of the cooling and the clothing hypothesis: Here it is assumed that hair loss is beneficial due to more cooling and that the negative effects of too much loss of heat were counteracted by the invention of artificial insulation.

Neoteny hypothesis: Neoteny denotes the retention of of juvenile physical characteristics in adults. Humans are characterized as retarded in development (compared to the apes) and mature more slowly. Additionally, it is assumed that some characteristics (here loss of hair) of juvenile or fetal apes are maintained.

Carrion-eating hypothesis: Another strange hypothesis, this assumes that man as a messy eater (like vultures and condors, which have naked necks) have an advantage of being hairless.

Sex-related hypothesis: This hypothesis assumes that hairless skin is more sensitive to stimuli like touch, temperature and pain. This would allow more sensitive social contacts, especially between man and woman, but also between woman and child. Pubic hair is not explained by this hypothesis.

Adaptation-against-ectoparasites hypothesis: Here it is assumed that naked humans are less prone to harbour ticks, fleas and other parasites which hide and live within fur. Apes have great social rituals of removing these within their group.

References:


Evolution of nakedness in Homo sapiens
The Hairless Mutation Hypothesis Explains Not Only the Origin of
Humanization from the Human/Ape Common Ancestor but also Immature
Baby Delivery
Genetic variation at the MC1R locus and the time since loss of human
body hair.