How does the protection circuit work? Do normal Li-ion batteries have it built in or do people usually add it?
Most Li-Ion cells do not have protection circuits, as most li-ion cells are in applications where they are being assembled into a pack (like your laptop) and it's much more effective to use a global protection circuit for the entire pack, rather than require 6 or 9 separate PCBs. You can buy 18650s and other size li-ion cells with protection circuits installed from a number of sources for flashlight applications. If you are planning on using them in the pack configuration they are in already, then leave the pack alone and take advantage of the protection circuit that is already installed. Keep in mind though that the PCB may have a maximum current limit so you are going to either be limited by the PCB as far as what you can run with it, or you are going to need to factor in the maximum safe discharge rate for the pack. I Personally suggest trying to keep your runtime in whatever configuration you decide to use it in at ~45 minutes or longer to keep the discharge rate safe.
If they are nominally 3.7V each, that's kinda weird that discharging them to less then 3.6V can damage them. Why is that?
The 3.7V rating is related to the average voltage delivered into a typical load for a li-ion cell through a typical discharge. There's no such thing as a battery that delivers a constant perfect voltage all the time into a veriety of loads, and there are hundreds of different applications and cell sizes and qualities out there so the actual discharge behavior varies in the industry. 3.7V is just a general average, just like with NIMH cells we call them 1.2V cells, when in fact, they charge to ~1.45V, and discharge to ~0.9V under a load, and average ~1.2V into typical loads, but there is a lot of variation from one brand to the next on how well they actually do under a load. Li-Ion actually charges up to ~4.20V open circuit, when a load is applied, the effective voltage drops to ~4.1V, and steadily declines to ~3.3V under a load before being completely drained. When the load is removed, then you will typically measure ~3-3.6V open circuit, anywhere in there means the cell is basically completely drained, it's best to try to keep the open circuit voltage above 3.6V for best cell health.
Dropping the voltage of a li-ion cell too low causes a sort of de-stabilization of the chemistry within. Having a proper number of electrons "chemically stored" within the cell keeps oxidation to a minimum, which increases cell health and life, overcharging and over-discharging throws this balance out of wack, and causes an increased rate of internal oxidation, which in the short term causes small increases in internal resistance and capacity losses, long term storage in an over-discharged state can actually lead to micro-shorting within the cell as the separators within the cell are literally eaten through by oxidation. Small shorts like this can cause pockets of heat build-up on a subsequent charge, the heat could further excite the chemistry, that in conjunction with a charge being applied could cause the micro-shorts to quickly expand into much larger shorts, which could quickly lead to thermal-runaway, the cell ignites and new chemical reactions begin, in lithium cobalt chemistry the combustion process actually generates it's own oxygen which continues to fuel the fire.
Scared yet? Don't be... We've had lots of people recover over-discharged cells, and quality cells can handle quite a bit of abuse before what I described above would happen. Keep your cells between 3V and 4.20V and keep track of their capacity over the years, discard when they are down to 80% of their initial capacity and you will be perfectly safe.
Eric