Check for vacuum leaks (bad ends on rubber tubes--normally you will hear some hissing from the leaks--start the engine up, set the controls to heat, then turn the engine off and listen for moving air). Many vehicles always have the heater core hot, but use doors to mix hot and cold air.
Grab the heater inlet/outlet lines... If the engine is well heated, controls set for heat, both hoses should be pretty warm--one may be warmer than the other. If both hoses are cold, or one is warm and the other cold--then you have a water flow blockage... Look in the radiator. Is there lots of rust (can block heater core)? If no rust, is there a lot of white power/deposit on the ends of the water tubes? If so, then the heater core may be blocked... If not, perhaps a heater hose has collapsed or the liner has failed. Is there a water valve to let water through the heater? Is the valve opening and closing?
Other possibilities, bad water pump (sometimes, water pumps just "stop" pumping at times--they look OK, but replace and everything works again). or rusted metal tubing to rubber hose connection (tube/casting filled in with rust).
Thermostat OK? Closed when engine is cold, open when the engine is hot (radiator stays cool until the engine heats up, then radiator gets "instantly warm").
Lastly, is engine running OK? Any missing, or excess pressure in the radiator system (sometimes smells like tail pipe of running engine). Any oil/moose looking foam in radiator? Could be a blown head gasket or other oil/combustion leak.
If none of the above, see if you can find a maintenance manual (library, dealer parts counter) for your car--The newer cars with electronics everywhere may have a debug/error indicator if something is wrong.
-Bill