Android :: Server Expecting The Code?

What is the best way to ensure people don't cheat when you use a web server (or something similar) to handle some of your application logic? A good example is a high score board. People play a game and when they are done, the application sends the score to the server to be recorded. However, if someone knows what your server is expecting, they can craft their own "high score" and post it to the server without having earned that score.

There are many similar situations in which a person could potentially ruin an application by communicating with the server in ways they shouldn't. As a developer with a web-backed application, what are the best ways to prevent this? Putting a key in the application and encrypting the message is one option. But it would not be ridiculously hard to crack even this system because the compiled application is available with the key. This would stop amateur hackers, but not persistent, experienced hackers.

What about all you developers out there? How do you make sure that web server requests were properly generated from your android application? Or do you just assume it will be OK and that no one has time to try to break your cell phone app? Is there a better system?