Note: This is a translation of my post WordPress Themes lokalisieren. Thanks to Ainslie Johnson for reviewing my translation.
Unfortunately the language used inside the templates was English, as it is for most themes available. To make a translation you need to go through each template file, find the English words and translate one by one.
In wordpress itself, localization is done by .po/.mo files. Hence there are localization files for a number of languages already. All you have to do, is to copy this file to your directory, change a parameter and wordpress can speak a new language.
So, why not use this mechanism for themes? There are very few existing themes working this way. More precisely, I only know of two Giraffe and NIkynik Blue. Even then, I was unable to find detailed documentation on how these themes were built.
Theme localization is very easy to do, when you manage to understand how wordpress and gettext work together.