How does a cell "know" the coding strand vs. the non-coding strand of DNA during transcription of mRNA?
This is determined by the promoter -- the DNA sequence to which RNA polymerase binds. It's assymetric, and the polymerase binds in a specific orientation, that determines the strand and the direction it will go once elongation begins.
Strands in DNA double helix (and other nucleic acids) are anti-parallel: one strand in the helix is in 5'->3' direction while another is in 3'->5' direction. RNA polymerase can only synthesize RNA in 5'->3' direction, and so it uses the 3'->5' strand as the template (the second DNA strand is, I think, completely ignored by the polymerase during synthesis).
From one promoter transcription of both forward and reverse genomic strands can theoretically happen. However, the two possible nascent RNA strands are synthesized outward from the promoter and away from each other (i.e. they are not overlapping).
During evolution position of some promoters (but definitely not all of the promoters in the genome) have evolved to be in the place were at least one of the two theoretically possible RNA products can be translated. Transcription in the opposite direction (i.e. away from the gene) actually frequently happens in eukaryotes. These RNAs belong to a class of promoter associated RNA, but but they were not shown to be translated (their function is largely unknown).
UPDATE (2015/02/19): New publication in Molecular Cell by Duttke et al. is demonstrating that genic promoters are "intrinsically directional" and, just as @Leon Avery commented here before, the divergent (i.e. bidirectional) promoters are actually two unidirectional promoters side-by-side, in reverse orientation relative to each other. So my above statement "From one promoter transcription of both forward and reverse genomic strand can theoretically happen" is incorrect. However, the authors also say that approximately half of gene promoter regions in HeLa possess this bidirectional initiation property, so it is still an important feature to keep in mind when thinking of transcription of eukaryotic genes.