Changing localization “on the fly”

So I got myself a blog, which I integrated nicely into my page. My challenge is now to integrate localization of the page (as in names, messages etc., I have an idea how to do with posts, i.e. tagging them) to change on the fly as user switches to different languege of my page.

Is it possible from themes (like overriding WPLANG?) itself, or I’ll actually need to hack the core to achieve this?