Ultra nationalism, which manifested via the ideology of Hutu Power, played a major role in the genocide. A core principle of Hutu Power was an idea concerning the origin of the Tutsi inherited from colonial rule, the Hamitic Hypothesis. Put forward by 19th century explorer John Henning Speke, it stated that the Tutsi were descended from a Middle-Eastern Semitic people who he believed migrated south to Ethiopia and further into Rwanda and Burundi - he believed they were inherently superior to the Hutu's and deserved preferential treatment.
Hutu Power espoused this belief and continually reasserted the idea that the Tutsi were foreign invaders not native to Rwanda. Leon Mugesera, a pamphleteer and an official of the ruling MRND (dominated by the Akazu), once said:
"[The Tutsis] belong in Ethiopia and we are going to find them a shortcut to get there by throwing them into the Nyabarongo river [which flows northward]" (From his Nov. 1992 speech - quote taken from ref 1)
This is just a brief outline of a central point - this is quite a complex issue as you can imagine. I've tossed a few useful references below, I advise you read them for more detail.