We present high-contrast observations of 68 young stellar objects (YSOs) explored as part of the SEEDS survey on the Subaru telescope. Our targets are very young ($<$10 Myr) stars, which often harbor protoplanetary disks where planets may be forming. We achieve a typical contrast of $sim$$10^{-4}$--$10^{-5.5}$ at an angular distance of 1arcsec from the central star, corresponding to typical mass sensitivities (assuming hot-start evolutionary models) of $sim$10 ${rm M_J}$ at 70 AU and $sim$6 ${rm M_J}$ at 140 AU. We detected a new stellar companion to HIP 79462 and confirmed the substellar objects GQ Lup b and ROXs 42B b. An additional six companion candidates await follow-up observations to check for common proper motion. Our SEEDS YSO observations probe the population of planets and brown dwarfs at the very youngest ages; these may be compared to the results of surveys targeting somewhat older stars. Our sample and the associated observational results will help enable detailed statistical analyses of giant planet formation.