Today I have receive a notice saying, "iPhone needs to cool down before you can use it." I live in the North East of the US and the weather starting to get cold. Will this have a permanent effect on my iPhone if it continues staying this message?
Probably a combination of a failing battery and the cold weather. Batteries perform worse in cold weather and if the battery is already on it's way out then the combination is probably enough for it to start dying early. Unfortunately the only solution is to replace the battery. You don't say what kind of phone you have, but if it's new enough to be in warranty then take it to apple and they'll replace it for you for free.
also, now that its so cold out and people use their phones mounted to car vents, dont have hot air blowing on the phone. that will cause the overheated message. if i need to have my phone near my vents in the car, the heat blows directly on it. to avoid this, i switch the air to floor only.