The acute disparity between increasing bandwidth demand and available spectrum, has brought millimeter wave (mmW) bands to the forefront of candidate solutions for the next-generation cellular networks. Highly directional transmissions are essential for cellular communication in these frequencies to compensate for high isotropic path loss. This reliance on directional beamforming, however, complicates initial cell search since the mobile and base station must jointly search over a potentially large angular directional space to locate a suitable path to initiate communication. To address this problem, this paper proposes a directional cell discovery procedure where base stations periodically transmit synchronization signals, potentially in time-varying random directions, to scan the angular space. Detectors for these signals are derived based on a Generalized Likelihood Ratio Test (GLRT) under various signal and receiver assumptions. The detectors are then simulated under realistic design parameters and channels based on actual experimental measurements at 28~GHz in New York City. The study reveals two key findings: (i) digital beamforming can significantly outperform analog beamforming even when the digital beamforming uses very low quantization to compensate for the additional power requirements; and (ii) omni-directional transmissions of the synchronization signals from the base station generally outperforms random directional scanning.