Why use a timestamp and how can someone know it's the correct one? Let's say A wants to send a message, so everyone who gets the message, can be assured that it's from A. A then sends a message message|timestamp|E(A_private_key, Hash(message|timestamp))

What are the benefits of timestamp? How can a person who gets the message know that it's the correct timestamp? Why just not send message|E(A_private_key, Hash(message))?
Actually, I guess that you are talking about digital signatures and not about public key encryption (since you want to have message authenticity and not confidentiality).

Whether using time-stamps or not makes sense depends on your application. Basically, the idea is that the verifier can determine when the signature has been issued and in particular that the message existed before some particular point in time. 

However, with your above mentioned approach, a verifier can not really be sure, since the signer ($A$) may include an arbitrary time-stamp (this does not necessarily be the correct one and could be "back dated"). Whether this is really a problem, again, depends on your application.

In order to tackle the above mentioned problem with "back dating" and thus to ensure that the message is correctly dated there are so called trusted time-stamping approaches. 

If $A$ uses trusted time-stamping based on digital signatures then basically $A$ lets a trusted third party (TSA - time-stamping authority) sign the message along with a time-stamp ($A$ only needs to send the hash value of the message not the message itself, if $A$ does not want to reveal the message) and then $A$ signs the time-stamp+signature from TTP+message with $A$'s own private signing key. Now, everyone in possession of $A$'s authentic public key and trusts the TSA can be sure that the message existed before the time-stamp.

You may also look here for a more detailed discussion on time-stamping.