In the following sentence, which relative pronoun would I use? Is this correct?
Nous sommes partis l'année que tu es né.
One of the difficulties arises due to the fact that in this case French requires specificity where English uses the unspecific "that". In French, you can't simply say "The year that I arrived" instead, you must say "The year when I arrived". Since you seem a bit confused as to the roles of "où", "que" and qui, allow me to offer a bit more information to help make things clear.
The french word "que", when it is used to bridge two clauses (sentence fragments), stands in for the object of the clause which comes after it. It can be roughly translated as "that" in most cases, which is omitted frequently in English. For example, "I have the book (that) you want" translates to "J'ai le livre que tu veux." In this case, the object of the second clause "Tu veux" is "le livre".
"Qui" is similar, however it replaces the subject in the clause after it. It roughly translates to "which" but in English it is often omitted. For example, "J'aime le livre qui s'appelle « Harry Potter »" translates to "I love the book which is called 'Harry Potter'", but more often in English would simply be said as "I love the book called 'Harry Potter'". (or even simpler, "I love the book 'Harry Potter'")
Finally, we are left with the correct answer, "Où". It means "where" but also means "when" in all cases where "quand" cannot be used. Remember that "quand" can only be used to ask a question "Quand pars-tu?" (When are you leaving?) or form a conjunction "Tu peux manger quand tu veux" (You can eat when you want). In all other cases, we must use "où". "L'année où je suis arrivé" means "The year that (when) I arrived."
"L'année où tu es né" is the correct way. To avoid confusion, you can say "L'année de ta naissance" instead.
Since I can't comment on the Tyg13 I would like to make an addition to the answer :
"où" has never, and will never refer to a specific time. "où" is refering to a place, and in most cases it is not good practice to use it when the subject is not strictly a matter of location. "Où es-tu ?" "Où ce trouve la bibliothèque ?", theses questions ask for a place, location is the important information. In "L'année où tu es né", the important information is not the location, but the time. That's why you can't use "où" and have to say it in another way : "L'année de ta naissance".
Using "où" to refer to a time is ok for a 10 years old child, but not for an adult.