An appropriate starting point is a xx1117. These are under $.50 USD and are rated up to 800ma and 15V input as Tom mentioned; it's when your input voltage goes over that 15V that you need a LM317 or LM780x as they can handle up to ~40V inputs. When you go over currents of 1A but less than 3A or your input/output voltage difference is high then an LM2596 switching regulator is a popular choice; you can find prebuilt modules all over eBay for a couple USD each. Over 3A usually means you'll be buying a power supply tailored for your project or using a power supply from an old computer, etc.
DVDdoug:
Switching designs are nearly 100% efficient. It's usually not necessary to calculate power dissipation (and it might not be possible to calculate accurately) as long as you stay within the voltage & current ratings.
That efficiency claim of 100% is not accurate; 80% would be more correct but some can get a little over 90% under ideal input voltage and load.