Suppose you use the international address function to search for the Bahnhofstraße. To sent this string to the web service, the characters first have to be converted to bytes. The character encoding is a mapping table from characters to bytes, and this table dictates which characters are converted to which bytes.
If you are using Latin1 encoding, the ß in Bahnhofstraße will be converted to one byte with numerical value 223. If you are using UTF-8, the ß will be converted to two bytes, 195 and 159.
Now, if the server and the client do not agree on the character encoding, the server can not convert the bytes from the client into characters. If the client and server do not use the same mapping table, character strings will become malformed.