Mobility may degrade the performance of next-generation vehicular networks operating at the millimeter-wave spectrum: frequent mis-alignment and blockages require repeated beam training and handover, and incur enormous overhead. Nevertheless, mobility induces temporal correlations in the communication beams and in blockage events. In this paper, an adaptive design of beam training, data transmission and handover is proposed, that learns and exploits these temporal correlations to reduce the beam training overhead and optimally trade-off throughput and power consumption. At each time-slot, the serving base station (BS) decides to perform either beam training, data communication, or handover when blockage is detected, under uncertainty in the system state. The decision problem is cast as a partially observable Markov decision process, and the goal is to maximize the throughput delivered to the UE, under an average power constraint. To address the high dimensional optimization, an approximate constrained point-based value iteration (C-PBVI) method is developed, which simultaneously optimizes the primal and dual functions to meet the power constraint. Numerical results demonstrate a good match between the analysis and a simulation based on 2D mobility and 3D analog beamforming via uniform planar arrays at both BSs and UE, and reveal that C-PBVI performs near-optimally, and outperforms a baseline scheme with periodic beam training by 38% in spectral efficiency. Motivated by the structure of the C-PBVI policy, two heuristics are proposed, that trade complexity with sub-optimality, and achieve only 4% and 15% loss in spectral efficiency.