For theme-based localization, look at the files in wp-content/themes/<your_theme_name>. That directory contains the various template files for a given theme. Plugins are located in wp-content/plugins.
It could be your theme's author has conveniently set up a language or constants file that you can easily modify. If so, then you can localize those strings. If not, you'll need to go file by file and search for the strings you want to replace.
Be careful only to replace outputted strings, not function names or internal constants. To be on the safe side, you might want to do this work in a copied version of your theme.
You'll also need to run your own localization support on version updates to the theme, as any updates have a good chance of overwriting any localization changes.
I hope this helps!