From the Google Webmaster Central Blog

I guess Google must have had a lot of questions on how search results are returned for special characters. For instance, does "Mexico" return results with "México"? Yes and No. If you browse from a country who's speech main language is english, it will return both, regardless of which one is used, but "Mexico" will have more results. On the flip side, if you were searching in Mexico and typed in "Mexico", it would return both spellings, but with more "México" results.

<quote>
The searcher's interface language is taken into account during this process. For instance, the set of accented characters that are treated as equivalent to non-accented characters varies based on the searcher's interface language, as language-level rules for accenting differ.

Also, documents in the chosen interface language tend to be considered more relevant. If a searcher's interface language is English, our algorithms assume that the queries are in English and that the searcher prefers English language documents returned.

This means that the search results for the same query can vary depending on the language interface of the searcher. They can also vary depending on the location of the searcher (which is based on IP address) and if the searcher chooses to see results only from the specified language. If the searcher has personalized search enabled, that will also influence the search results.
</quote>

The article also goes on to how you can restrict searches to strict versions of the word

<quote>
To obtain search results for only a specific version of the word (with or without accented characters), you can place a + before the word.
</quote>

Link:
http://googlewebmastercentral.blogspot.com/2006/08/how-search-results-may-differ-based-on.html

[Corrected typo in title – Tony]

As a side note to this, Garett Rogers found some neat properties to the Google translate service, possibly a glimps into the future bable fish.

http://blogs.zdnet.com/Google/wp-trackback.php?p=312