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 the first 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 FML, with proven performance bound and guaranteed convergence. FML exploits coarse user location information and aggregates received data to learn from and adapt to its environment. 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 minutes of deployment by learning from the available context. Moreover, FML remains within 5% of the optimal performance by swift adaptation to system changes such as blockage and traffic.