So how does it work? how comes those people who marry USC get away with it even after having been out of status for decades?
To give you the brief overview: Section 245 of the INA, as others mention, covers Adjustment of Status. 245A says that one cannot adjust status if they have been out of status, illegally present or employed without authorization since their last entry to the US. Then, the INA proceeds to carve out three major exemptions:
245C (I may have this subsection wrong) says that an Immediate Relative (spouse, minor child or parent) of a US citizen is exempt from the restrictions in 245A, and their I-485
cannot be denied on this basis, no matter how long they have been out of status or illegally employed. Note that this is a non-discretionary clause; USCIS cannot selectively enforce it. No matter how long you have been employed or out of status, USCIS cannot deny your case.
245K is similar to 245C, except that it only applies to employment-based applicants, and the period of forgiveness is limited to 180 days. Again, it's non-discretionary relief, so USCIS cannot deny your I-485 if you've been out of status or illegally employed (like a gap between EADs) for less than 180 days.
Finally, 245I is similar to 245C, in that it allows illegal presence, illegal employment, etc. for an unlimited period. It applied to Family Based and Employment Based immigrants. Unlike 245C, I believe it also allows forgiveness for aliens who entered the US without Inspection. To get 245I relief, one filed an I-485A supplement and paid a $1000 fine. However, 245I had a "sunset" clause - in order to qualify for 245I relief, one needed to have a priority date of April 30th, 2001, and be physically present in the United States on December 22nd, 2000.
For this reason, there are almost no people left who qualify for 245I relief. For those of you filing an I-485 based on a DV win, note that you are not eligible for any of these forms of relief, so pay careful attention to remaining in legal status and not working without authorization.
I am also not an attorney, so please consult an attorney if you fear you may be in (or about to get in) a situation that makes you ineligible to adjust status.
Does being out of status (F-1) automatically mean being illigaly present?
If USCIS sends you a notice, then yes.