(Expanding on manojlds's answer.) The simplest thing to attach a message is indeed to un-stash and re-stash with a message, there is a git stash branch command that will help you doing this.
git stash branch tmp-add-stash-message
git stash save "Your stash message"
The only drawback is that this stash now appears to originate from the tmp-add-stash-message branch. Afterwards, you can checkout another branch and delete this temporary branch.
Of course, this assumes that your working copy is clean, otherwise you can stash the current changes :-)
Here's some commands to help you pop and save again as @manojlds suggests:
git stash #save what you have uncommitted to stash@{0}
git stash pop stash@{1} #or another <stash> you want to change the message on
# only if necessary, fix up any conflicts, git reset, and git stash drop stash@{1}
git stash save "new message"
git pop stash@{1} #get back to where you were if you had uncommitted changes to begin with