It actually was a gradual process. It was primarily driven by his personal popularity in a society where ancestor worship has long been an integral element. Moreso than his fame as a general, his personality traits (loyalty, bravery, honesty) appealed to traditional Chinese sensibilities.
Among the general population, Liu Bei and Guan Yu have set a more significant moral standard than Confucius or Mencius.
- Yong, Jin, and Daisaku Ikeda. Compassionate Light in Asia: A Dialogue. IB Tauris, 2013.
These factors led to his popularity steadily increasing, before he really became a deity per se (as opposed to a folk hero venerated in the tradition of ancestor worship). So that by the Song Dynasty, the bureaucrat-author Hao Jing wrote that:
(rough translation) His righteousness and strength of character is known throughout the world. Hence his temple brings fortune and wards off disaster, and people respect his might. The provinces of Yan, Zhao, Jin and Chu are particularly pious. Every county, province, city and village has his temples.
Between the Song and Yuan dynasties, a tradition of historical fiction flourished in China. The Three Kingdoms era from which Guan Yu hailed were one of the most popular topics, and this greatly aided the spread of his fame.
It is well known that the spread of the worship of Guan Yu as a folk deity beyond the confines of sectarian religion was communicated in the vernacular novels and plays of the Song-Yuan transition.
- Duara, Prasenjit. The Global and Regional in China’s Nation-Formation. Routledge, 2008.
Therefore, when he received his imperial (divine) title during the Ming Dynasty, it was already after centuries of popularity.
For references on the deification process described previously, see:
关羽崇拜硏究 by 蔡东洲 & 文廷海