I remember doing Punnet squares in high school, and it was neat and clean. A combination of two alleles led to one result--the dominant dominated, or the two recessives were expressed.  But it seems like almost any interesting trait (who cares about widow's peak and cleft chins?) is caused by both alleles being expressed and combined with many other alleles. So how DO two alleles, one from dad, one from mom, interact? Do they both both code for protein? Does one turn the other off, usually, ever? What are all the possibilities for two different alleles relating?

There are several possibilites with two alleles.  Let's consider first the simple dominant/recessive case of a hypothetical genetic locus involved in red (dominant) vs. white (recessive) flowers.  Possibility one is that the dominant allele is made into protein and can convert a colorless molecule into red pigment, the recessive allele is also made into protein but cannot convert the molecule into pigment, it remains colorless.  Possibility two is that the recessive allele isn't made into protein at all - perhaps there is a mutation in its promoter region that inhibits mRNA synthesis.  Possibility three is that the protein coded by the recessive allele actually converts a red molecule into a white pigment (or otherwise covers up an underlying red color).  In this case, the dominant allele makes a protein that inhibits this process, for example by binding to the recessive protein or the precursor to the white pigment or by inhibiting the recessive protein synthesis. 
Another scenario is where you have co-dominance.  In this case, both proteins can be active and have different activities: perhaps flowers that have both alleles are pink.  

You can see from the above examples that the proteins coded by the alleles can interact or there can be other downstream physical interactions.  There are a LOT of other possibilities.  I would recommend purchasing a used genetics textbook if this topic is interesting to you as there are many many other factors to consider in thinking about genetic interactions.

Hi Matt -
Anja's not even describing to you the weird cases.  To give you some idea of how complicated it can be, there is this outrageous phenomenon known as transvection that's been described for some fruit fly genes (and possibly other species, but I know flies best).  Basically, a gene consists of a couple of parts.  There is a protein coding sequence that spells out what amino acids in what order.  There is a short sequence called a promoter that sits in front of the protein coding sequence, and polymerase binds to it and then reads along the coding sequence to make RNA.  There are also enhancer sequences somewhere nearby that bind proteins that help recruit (or inhibit) polymerase binding to the promoter, these spell out when and where the gene is expressed.  Not surprisingly, if you delete either the enhancer, or the protein coding sequence, the gene is dead, no protein gets made, game over.  However, for certain genes, if you combine one allele in which the enhancer is deleted but the coding sequence is intact with another allele in which the protein coding sequence is deleted but the enhancer is intact, you get normal, wild type gene function.  The enhancer from one allele loops over to the other allele and recruits PolII to the promoter so that you get transcription.  So there are a few cases where its not dominant/recessive, or semi-dominant, but null + null = wild type.  And this is just one example of the ways alleles can interact.