I guess it simply uses "http://$language.wikipedia.org/wiki/$whateverthetextis".

The most correct, but convoluted way would be to use node author's language to look up the entry, get the "read this in another language", and select the link according to the reader's language. If the reader's language doesn't have an entry there, hmmm.... select according to a preference list (reader's browser or so)?

Easiest would be to stick to english - we non-native speakers are already used to that, and can press the "read in another language" ourselves ;-)

I'm beginning to think it's wikipedia that is doing this all wrong. But, i'm not even sure there would be a right way, unless they used shortcuts instead of titles.

I'd say it's more of a conceptual problem. The headword has to be in some language.
To resolve this, one needs to introduce a language-independent lemma identifier (ha! gives a nice acronym!) - but that's just yet another language itself... e.g. UDC