Finding all normal subgroups of a group
(i) Conjugacy classes are certainly useful, since a normal subgroup must be a union of conjugacy classes. There are other ideas that can come into play: once you know a proper normal subgroup $N$, by taking the quotient you can obtain information about $G$ from information you may find in $G/N$, which will hopefully be easier than working directly in $G$ because $G/N$ will be smaller than $G$.
(ii) In fact, that is one important reason for finding all normal subgroups: being able to look at the quotient, and thus obtain information about $G$ by looking at groups that are smaller than $G$. Another is that the normal subgroups are closely associated with all possible images of $G$ under homomorphisms. Both of these facts are part of the Isomorphism Theorems.
Right now you are probably engaged in computation and getting familiar with techniques for working with groups in general, and $D_n$ in particular; the importance of normal subgroups will likely emerge as you start using groups. For example, normal subgroups are extremely important when you are considering Galois groups (which help you study fields and field extensions).
I'm assuming you want to know more about group theory, so here is an answer to point you to some of the interesting things that you can learn if you are interested in computing with finite groups.
(i) If you have the conjugacy classes and there are not too many, then writing normal subgroups as unions of conjugacy classes is fast and easy. This is often the case when you only have access to a group through its character table, such as when the Suzuki and the sporadic simple groups were being discovered, and we wanted to understand some of their (non-simple) subgroups.
For a typical finite group given concretely as a permutation group, you use a special type of induction working along what is called a chief series, where you find a maximal chain of normal subgroups. It turns out there are some fairly easy ways to find these: for a solvable group, or any group G with an abelian quotient group, you can fairly easily and concretely find the derived subgroup, [G,G]. The quotient group is an abelian group, so every subgroup between the whole group and the derived subgroup is normal. You then take the derived subgroup of the derived subgroup, but now you only take subgroups that are normalized by G/[G,G]. The action of G/[G,G] is relatively plain and easy to understand, so these "invariant" subgroups are pretty easy to find. To finish the inductive step, you need to find the normal subgroups of G/[[G,G],[G,G]] that don't contain [G,G], and this can be done by a slightly easier version of the general subgroup lattice algorithm using what is called the first cohomology group, or "derivations" (basically derivatives for groups, and related in a way to the derived subgroup). When you reach the point where the group is its own derived subgroup, a perfect group, then a second algorithm begins, that identifies the simple groups involved in the top of the group, and then constructs the solvable group below them. Sometimes you even have to repeat those last two steps, but not for groups of order less than 6024 ≈ 4.7e42 or so.
(ii) Often in mathematics, you want to use "induction". A normal subgroup is one of the two main ways to do induction in group theory. Usually it is not necessary to find all normal subgroups, but rather a single (nice) chief series will do. Some groups only have a single chief series (a fair number of dihedral groups are like this), and so finding the chief series and finding all normal subgroups is the same question. You might try the symmetric group of degree 4 and order 24 as an example.
Finding normal subgroups of a group is a first step towards understanding how it "factors" into simpler groups, analogous to finding prime factors of a number. To understand a group it then suffices to understand i) the pieces it's built out of (the simple groups in its composition series) and ii) how those pieces fit together.
In your case it is also just a good exercise in becoming familiar with groups and with basic constructions associated to groups. Also, like Weltschmerz says, you should think of knowing the normal subgroups as the same thing as knowing all the quotient groups of a group, and the quotient groups of a group are like its "shadows" - they reveal some, but not all, of the structure of the group, and putting them together one gets a picture of the whole thing.
Very vague answer to (ii) (I'm taking this course myself): if you find all normal subgroups of a given group, then you know all its quotient groups, since quotient groups are defined through normal subgroups only - if you consider all left (or right) cosets of a given group, that isn't normal, they may not conform a group. And many theorems that follow in the theory are based on quotient groups.