All of which is good advise. Don't overlook your heater core. If it is partially clogged then it can cause the same symptoms. you can run a chemical cleaner through it and see if that helps. I have noticed that the thermostat can be at fault also. But if you have a check engine code for the water temp sensor that may be the problem. first thing, makes sure your coolant level is full.
Mouse, Phoenix Tuning