You have encountered two "hard" problems: authentication and authorization. There is plenty of information online on thes topic, but in your case I think your problem goes back to the design of the app.
Let us start with two questions:
- How do you know whether user is allowed to post a high score? (Authorization)
- How do you know the connection to your server comes from an actual game user and not somebody impersonating the game like in your Java example? (Authentication)
Before you try to re-invent the wheel, be aware that there are many libraries that do just that, with the added benefit of being mature, tested, working and well documented.
Not knowing the details of your app, here are a few suggestions:
- Let users play in 'solo' mode or in 'online' mode. In the former mode the game is standalone and does not need to make any network connections (good for privacy-aware users). In the latter case users SHALL register with your server.
- Once a user is registered (login/password) and you have verified they actually are a "real" user to some extent (e-mail responder, text message, etc.), your server can send back a 'token' to play.
- When the app wants to send its high score to your server it MUST authenticate itself by providing the token in a manner similar to what user @mike-mackintosh described in his answer.
- All communications to/from should obviously be encrypted with TLS or other forms of strong crypto.
- Your app should validate the certificates to avoid man-in-the-middle attacks.
The scenario is simplified: of course an attacker with enough resources could register a fake account, reverse engineer your app, determine the message to use and send bogus data to your server. To prevent it you'll need to ask the platform to verify that the app hasn't been tampered with, which in turn means extending the chain of trust to the operating system running the app, and so on. In the end it gets complicated (ever heard of "trusted computing" and digital rights management?) and depends on the value you're trying to protect.
Another avenue of research could be some form of server-side validation. For example, every time a user posts a score higher than X, they must also supply "proof" that they unlocked a certain achievement e.g. a random string that is saved in the user profile when they reach a specific point in the game. In this case you can double-check server-side that the user did actually pass the previous achievements earlier on.
You can spice things up furtner by generating the 'level' tokens by combining the phone's IMEI with a random key and using some form of public key encryption so that each user is tied to their phone. Which would work, unless somebody were using a custom ROM for android that allows tweaking the phone's IMEI, and so on.