It was in large part due to the French Revolution and Napoleonic Wars.
First, France had a revolution that led to the composition of the national anthem, La Marseillaise, that started French national feeling.
Napoleon's invasion of Germany, and the creation of the Conferation of the Rhine consolidated a bunch of "church" holdings into far fewer "states" that later formed the basis of German nationalism.
The creation of the Duchy of Warsaw led to a (temporary) resurgence of Polish nationalism.
The invasion of Russia and ultimate defeat of Napoleon stirred up Russian national feeling, as outlined in "War and Peace. To perhaps a lesser extent, this was true in Austria and Prussia as well.
Napoleon's invasion of Italy supported the continued consolidation of much of that country into a few power blocs (e.g. the Papal States, Naples-Sicily, etc.), mostly united against the "outsider."
Although he crowned himself Emperor, Napoleon had piggybacked on the French Revolution, and he was basically a "revolutionary" in the sense that he was a "leader" with non-royal blood. That paved the way for "similar" leaders like Greece's Rigas FaraoisRigas Feraios or Hungary's Lajos Kossuth.
Admittedly, these examples were from western Europe in the first half of the nineteenth century, but they set examples for eastern Europe, and in the second half of the century.