The first name which Metallica had in mind for "Cure" was "Believe".

Album:
Load

The demo:
The reason for that the song's demo was named "Believe" is because of the repetition of the verse "I Do Believe" in the lyrics.

The subject matter:
The song is about the wish of getting a cure from a difficult situation.

For example:
"He thinks the answer is cold and in his hand"
"He takes his medicine"
# 1 - He thinks a gun is the answer to his problems he's holding in his hand
# 2 - An alcoholic who believes that the next cold drink is the answer to his problems

"The man takes another bullet"
"He's been fooled again"
# 1 - He loads a bullet inside the gun, but he's wrong about that solution
# 2 - He has been fooled that alcohol would help him