Need some help to design power supply for custom Arduino PCB
Yes. Those regulators you linked are linear regulators. (Switching regulators can heat up too, but we'll leave that for another time.)
Drawing 600mA from a 9V makes for a very sad (and short-lived) 9V, at least for a standard 9V (an Energizer 522 capacity is &lt;400mAh @ 500mA discharge rate). Much better to use a stack of AA batteries (much higher current capacity).
At 2A, you are dissipating 2A*(9V-5V)=8W. Yes, you need a well-designed thermal plane (the datasheet can tell you how to calculate temperature rise). You cannot just put a heatsink on top of a DDPAK, the thermal resistance through the top of the case is not good.
This is too broad of a question. You have linked linear low dropout regulators. There is no single "perfect" regulator type. To second FakeMoustache: given your experience level, if you want to use a switching regulator, you should buy an existing module (designing a switching regulator into a board requires considerably more domain knowledge than does a linear regulator).