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.
Timestamps allow the recipients to know the order in which messages from an honest party were sent. This is sometimes important in cryptographic protocols.
Timestamps sometimes allow the recipient to know that a message from an honest party has been replayed. This is important in cryptographic protocols.
These properties sometimes allow protocols using timestamps to be more efficient than protocols that are not using timestamps.
You can guess it's the correct timestamp if it's within a few seconds (or minutes) from the current timestamp. At the very least you can assume that the timestamp of the message that just came in must be greater than the timestamp of the last one.
Similarly, if the timestamp points to the future by any reasonable margin (a few seconds) you know the other computer is either out of synch or may be trying to do something fishy. All of the above assume the two entities communicate in real time (eg. a chat program) instead of asynchronously like, say, email. But even in email, you can't say that you sent the spec yesterday! when you only just hit the send button.
In case you aren't using a signature scheme but just send a plain hash, you can assume the timestamp gets digested in the hash for plainly because it's part of the data (and we want to detect transmission errors/alterations etc).
When you do sign the message and the timestamp, you also prompt for temporal verification: Aye, 'tis I who send thee thy email, not too long ago. If you didn't put the timestamp in you only say Aye, 'tis mine.
In SIV type crypto-systems (like AES-SIV, etc), where initialization vectors are derived from the plaintext of messages, a timestamp can be concatenated with the plaintext to either potentially improve the cipher's nonce reuse/misuse resistance, or to reduce the likelihood that two identical plaintexts that are temporally separated will produce the same ciphertexts. The others answers describe well ways to gain confidence in timestamp correctness.
