When it comes to API authentication, those are the three most used models (in random order):
Credentials are sent with every response.
Credentials are sent once to generate an access key. The access key is then sent with every request.
Credentials are sent once, and then a session (relying on cookies) is used to avoid repetitive authentication. Since one of the properties of REST is that it is stateless, this shouldn't be considered as REST and won't be discussed in this answer.
The first one has a benefit of simplicity: you don't have to deal with the additional access key, its generation (it should use cryptographically secure pseudo-random number generator), its validation and its invalidation (how long should the client stay inactive for the key to become obsolete?).
The drawback, on the other hand, is the impact in terms of performance. Instead of verifying credentials once, you should verify them at every request, which also means that you probably cannot use PBKDF2 with a high number of rounds, since it will take too much CPU power and slow down the API tremendously).
Note that in the first case, you will be sending credentials through HTTP's Authorization header. In the second case, Authorization header should not be used to send the access key, since it's not its purpose. Including the access key in the URI seems to be a common practice, although it results in long, cryptic URIs and pollutes HTTP logs.
Should those be the same end user credentials different for every user or should they be sort of "app credentials" for accessing services?
You shouldn't use user password. If you do it, this means that you stored it, somehow, somewhere, in plain text, and that's a very, very bad practice.
There are two ways to use an API:
Per-user usage. This is often the case where the third-party API is accessed through JavaScript on client side. For instance, if your website allows a user to view the list of his friends from another website, the list being loaded through JavaScript by calling this other website API, you'll usually have a per-user usage.
In this case, there will be an association between the API account and the user account, so each user can access the API using a specific (randomly generated) client ID and the corresponding (cryptographically secure randomly generated) access key. The API should rely on the access key as its authentication means, but in any case should it receive or request the original user's password.
Per-application usage. This is often the case where you, and not your users, are using the third-party API. For instance, if you need to access some financial data, generate the reports and then sell those reports to the users (given that every paying user will have the same report), you're in this case.
Here, you'll have a single client ID and the corresponding access key. You'll need to store them securely on your server and under no circumstance share it with your clients.
