We present first results from the Palomar Adaptive Optics Survey of Young Stars conducted at the Hale 5 m telescope. Through direct imaging we have discovered a brown dwarf and two low-mass stellar companions to the young solar-type stars HD 49197, HD 129333 (EK Dra), and V522 Per, and confirmed a previously suspected companion to RX J0329.1+0118 (Sterzik et al. 1997), at respective separations of 0.95 (43 AU), 0.74 (25 AU), 2.09 (400 AU), and 3.78 (380 AU). Physical association of each binary system is established through common proper motion and/or low-resolution infrared spectroscopy. Based on the companion spectral types, we estimate their masses at 0.06, 0.20, 0.13, and 0.20 Msun, respectively. From analysis of our imaging data combined with archival radial velocity data, we find that the spatially resolved companion to HD 129333 is potentially identical to the previously identified spectroscopic companion to this star (Duquennoy & Mayor 1991). However, a discrepancy with the absolute magnitude suggests that the two companions could also be distinct, with the resolved one being the outermost component of a triple system. The brown dwarf HD 49197B is a new member of a growing list of directly imaged sub-stellar companions at 10-1000 AU separations from main sequence stars, indicating that such brown dwarfs may be more common than initially speculated.