Millimeter-Wave (mmWave) bands have become the de-facto candidate for 5G vehicle-to-everything (V2X) since future vehicular systems demand Gbps links to acquire the necessary sensory information for (semi)-autonomous driving. Nevertheless, the directionality of mmWave communications and its susceptibility to blockage raise severe questions on the feasibility of mmWave vehicular communications. The dynamic nature of 5G vehicular scenarios and the complexity of directional mmWave communication calls for higher context-awareness and adaptability. To this aim, we propose an online learning algorithm addressing the problem of beam selection with environment-awareness in mmWave vehicular systems. In particular, we model this problem as a contextual multi-armed bandit problem. Next, we propose a lightweight context-aware online learning algorithm, namely fast machine learning (FML), with proven performance bound and guaranteed convergence. FML exploits coarse user location information and aggregates the received data to learn from and adapt to its environment. Furthermore, we demonstrate the feasibility of a real-world implementation of FML by proposing a standard-compliant protocol based on the existing architecture of cellular networks and the forthcoming features of 5G. We also perform an extensive evaluation using realistic traffic patterns derived from Google Maps. Our evaluation shows that FML enables mmWave base stations to achieve near-optimal performance on average within 33 mins of deployment by learning from the available context. Moreover, FML remains within 5% of the optimal performance by swift adaptation to system changes (i.e., blockage, traffic).