Find out the history of a script execution on Linux box

Without real auditing activated, in the general case the answer will be that this is not possible.

If the users you are concerned about cannot change the script, you easily can add a very simple logging function with the help of the logger command.

Add a line like the following to your script:

logger Myscript was run by user $USER

You can't do this retrospectively unless you had auditing enabled. Going forward you could enable auditing or you could modify the script to log it's activity.

Update for your update:

If you know the user you may get something out if their ~/.bash_history but it's not really a good place to look as it is easily edited and bypassed see here. Auditing on the other hand is much more difficullt to tamper with.