Are male and female brains physically different from birth?
Short answer
Yes, men and women's brains are different before birth.  

Background
First off, learning effects versus genetic differences is the familiar nature versus nurture issue. Several genes on the Y-chromosome, unique to males, are expressed in the pre-natal brain. In fact, about a third of the genes on the Y-chromosome are expressed in the male prenatal brain (Reinius &amp; Jazin, 2009). Hence, there are substantial genetic differences between male and female brains.  

Importantly, the male testes start producing testosterone in the developing fetus. The female hormones have opposing effects on the brain as testosterone. In neural regions with appropriate receptors, testosterone influences patterns of cell death and survival, neural connectivity and neurochemical composition. In turn, while recognizing post-natal behavior is subject to parenting influences and others, prenatal testosterone may affect play behaviors between males and females, whereas influences on sexual orientation appear to be less dramatic (Hines, 2006). 

The question is quite broad and I would start with the cited review articles below, or if need be, the wikipedia page on the Neuroscience of sex differences.

References
- Hines, Eur J Endocrinol (2006); 155: S115-21
- Reinius &amp; Jazin, Molecular Psychiatry (2009); 14: 988–9