Ensure web service only accessed by authorized applications
The bottom line is that you will need to embed a secret into your app. It is an unfortunate truth that DRM (which is more or less what you are trying to achieve) is impossible. A person with access to your app will always be able to recover the embedded secret, no matter what you do to protect it.
That said, there are plenty of things you can do to make your embedded secret very difficult to recover.
Construct it at Runtime - Do not store the secret in a string or configuration file anywhere in your app. Instead derive it from a series of computations at runtime. This stops attackers from simply browsing your app with a hexeditor.
Never Send it Over the Wire - Use a challenge-response system of some kind with a >128bit nonce, that way an attacker cannot MitM the SSL stream (which is easy when he controls the mobile device remember) and see the secret in the clear.
In any case, try to find a tried and tested key-scrambling mechanism and authentication protocol. Do not roll your own.
Mostly you cannot check that this is "your app": reverse engineering works, so whoever has access to your app (e.g. he can download it on his phone) can pluck at its entrails and emulate it with his PC. @Lynks gives you some hints about how this reverse engineering can be made a more frustrating endeavour, but don't fool yourself: if the attacker is sufficiently motivated, these mechanisms will slow him down by at most a couple of days.
When there is no good answer for a question, it can be worthwhile to shift the ground so that the question changes. Here, the core problem with trying to make sure that "your app" is what runs on the client side is that there is such a thing as "your app": if somebody opens up the contents of that app, he learns everything that is to learn about all instances of that app everywhere.
So here is an attempt at a solution to your problem. Tag each app instance with a distinct value. "Tagging" here means that when the user downloads the app, some token is embedded into the app, and a new token value is created for each download. So that each user gets his own app with token. The idea being that the token will have to be presented to your server for account creation, and if your server sees too many requests with the same token, then it can automatically reject them -- banning that specific token.
Then, to keep on creating many accounts automatically, the attacker would have to also automate the download of fresh app instances (each with its own token value) and retrieval of the token value out of the downloaded app. Assuming that your server is at the other end of the app download, you can also detect such mass-downloading and block it from there.
For this scheme to work, you must be able to create token values on the app-download server, on demand (this might be difficult to setup with the apps installation system on existing smartphones, though), and such that the account creation server can decide whether a token value is genuine or not. HMAC is the right cryptographic tool for that.
Be aware that this kind of solution is nowhere near perfect. These are games and tricks to "raise the bar" for the attacker: if you design and install a system like the one I describe, then a successful attacker will have to automate the app download from many distinct IP addresses, to keep under the radar of your heuristics for detecting such things; then also automate the reverse-engineering to recover the token values (use the techniques explained by @Lynks for that); then forward the values to his bots which create accounts. All of this is still theoretically feasible: after all, human users can download the app and create accounts, and there is no way to really make the difference, from the outside, between an average human user, a chimpanzee and a bot.
But if you can make the attack sufficiently complex that the attacker deems it "not worth the effort", then you win.
If I was writing a website, I would use Captcha to stop my database from being filled up with bogus accounts via script.
So include that in the API. When a user wants to create an account:
- The client requests a CAPTCHA.
- The server generates a CAPTCHA, stores it, and sends a copy to the client.
- The client presents the account creation form, along with the CAPTCHA.
- The user fills in the form and answers the CAPTCHA.
The client requests that the new account be created, and sends the CAPTCHA answer with that request.
- If the CAPTCHA answer is wrong, the server deletes its copy of the CAPTCHA (so the client can't try again) and responds with an error.
You could also use something like HashCash to make it harder for someone to mount a brute-force attack, just make sure the HashCash can be generated faster than a user could reasonably finish the form.