Enabling the high data rates of millimeter wave (mmWave) cellular systems requires deploying large antenna arrays at both the basestations and mobile users. The beamforming weights of these large arrays need to be tuned to guarantee sufficient beamforming gains. Prior work on coverage and rate of mmWave cellular networks focused mainly on the case when basestations and mobile users beamfomring vectors are perfectly designed for maximum beamforming gains. Designing beamforming/combining vectors, though, requires training which may impact both the SINR coverage and rate of mmWave cellular systems. This paper characterizes and evaluates the performance of mmWave cellular networks while accounting for the beam training/association overhead. First, a model for the initial beam association is developed based on beam sweeping and downlink control pilot reuse. To incorporate the impact of beam training into system performance, a new metric, called the effective reliable rate, is defined and adopted. Using stochastic geometry, the effective reliable rate of mmWave cellular networks is derived for two special cases: with near-orthogonal control pilots and with full pilot reuse. Analytical and simulation results provide insights into the answers of three important questions: (i) What is the impact of beam association on mmWave network performance? (ii) Should orthogonal or reused control pilots be employed in the initial beam association phase? (iii) Should exhaustive or hierarchical search be adopted for the beam training phase? The results show that unless the employed beams are very wide or the system coherence block length is very small, exhaustive search with full pilot reuse is nearly as good as perfect beam alignment.