Besides the power dissipated by the regulator (voltage drop times current passing through it) there's one more to look out for: oscillation. It is possible for linear regulators to go into oscillation which heats them up, although with 78xx types I find it rather uncommon. The caps close to the regulator from input to ground and from output to ground (usually some 220nF and 100nF) should be able to supress that. Datasheets tell you that you only need the caps if the input and output lines are long (>30cm), but it's not a bad idea to use them always.