How did sneezing evolve?
Sneezing itself is a part of long story of human evolution.

Sneezing for early humans was as common as eating is for us. Early humans lived in caves which were full of dust and insects so whenever they wake up from sleep they sneezed intentionally to remove the dust and small insects from their nose, slowly this behaviour of early humans was proved to be beneficial and muscle memories remembered the Activity as a daily routine work and performed it to remove dust and any irritant in their nose or nasal cavity. 
As they evolved they passed on their daily routine works to their descendants and this was also passed on , this way sneezing was slowly incorporated into the muscle memories and it exists till now as a way to relax is from external allergens.

There are several other theories too about evolution of sneezing and it itself demands great research .
 There is also a video on Veritasium on YouTube regarding the Sneezing whenever one sees light , this video too discusses this theory.
You should check that out too.