Transforming a theme or plugin to handle several languages is something that can increase the reach of your code manifold, by encouraging the usage of local versions.
The process is extremely well documented on Urban Giraffe’s post (the post is four pages long, check the navigation at the bottom of the post) which includes mostly everything, from the GNU gettext usage on WordPress, to configuring and generating .pot files. Highly recommended reading, together with Ryan’s post, a shorter overview of the process.
At some point, after having inserted all the proper function calls, you will want to test your theme or plugin for localization. This is where the newly released Pig Latin plugin comes in handy: It will allow you to check if all the strings in your plugin or theme are translatable by translating all messages to Pig Latin. For example, if your code is correct, the string “Edit Pages” should appear as “Editay agesPay“. In short, it aims to show text both noticeably different than English and readable. This way you can spot strings, which aren’t translatable, while the interface is stil usable.
Be aware that everything that’s translatable in your WordPress installation will show up as Pig Latin, including the dashboard.