Millimeter wave (mmW) bands between 30 and 300 GHz are considered a promising candidate for next-generation cellular networks to relieve spectral congestion in conventional cellular frequencies. However, cellular communication at these frequencies will likely require highly directional transmissions to achieve suitable signal range. This reliance on directional beamforming 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. This paper proposes a directional cell search procedure where each base station periodically transmits synchronization signals in randomly varying directions. Detectors are derived for this synchronization signal based on a Generalized Likelihood Ratio Test (GLRT) for the case where (i) the mobile has only analog beamforming (where the mobile can 'look' in only direction at a time) and (ii) digital beamforming where the mobile has access to digital samples from all antennas. Simulations under realistic parameters demonstrate that mobiles may not be able to achieve suitable detection performance with analog beamforming alone. In contrast, digital beamforming offers dramatically better performance. We argue that the additional power consumption cost of digital beamforming can be offset by using very low quantization rates with minimal performance loss, thus arguing that low-rate fully digital front-ends may be a better design choice for directional cell search.