I'm going to answer this from an aviation safety regulation viewpoint only. There are many broader considerations, such as criminal juristictions, employment, and environmental laws, which will have differing answers. I'll also add that my experience is with the Australian situation, but I don't think it varies too much around the world - happy to be corrected.
So with all that considered, the answer is... sort of both! The short answer is that they must follow the direct operating procedures of the country they are flying in, but some "back office" regulations do not apply.
Firstly to ICAO. This organisation isn't really concerned about individual airlines. Their primary purpose is to set international standards for the individual regulators to implement. But these Standards and Recommended Practices (SARPs) are not enforceable - individual states can simply lodge a 'difference' and continue to do their own thing. Another important job of ICAOs is to basically regulate the regulator, giving them a rating on how safe they are. The FAA and EASA also conduct their own audits for the same purpose.
Each airline needs to be certified in its home country with an Air Operators Certificate (or Part 121 Certification, or the many other variants around the world). Part of this process involves approving pretty much every single procedure the aircraft would ever do in normal operations - including the procedures at international ports. That means that for an Australian airline wanting to fly to LAX, the Australian regulator CASA has to inspect the port and approve it for use, checking that what the airline has proposed complies with the local airport procedures.
So, once the operations at LAX have been approved by CASA, the airline then approaches the FAA for a Foreign AOC/Part 121 approval etc (I'm not certain of the US naming convention). This certification process for a foreign certificate is almost always no way near as thorough as the full version. A lot of it depends on the home countries regulator and their status with ICAO or the FAA/EASA. If the FAA knows that the oversighting country is up to scratch, issuing the foreign certificate might just be a tick and flick exercise.
This 'foreign' status of this approval is key to your question, because many regulations are written like "the Part 121 operator must..." and NOT necessarily "the Foreign Part 121 operator must..."
Take a breath now and try to follow this. In the majority of occasions, the foreign approval says that the airline must operate in accordance with what has been approved by CASA. But, the procedures which CASA has approved are already tailored to LAX-specific operations! So you can see that the Australian airline has to obey the conditions of its FAA approval, which is to follow the operations set by CASA, which is to follow the US procedures!
But what if CASA and the FAA have differing regulations? We do have different requirements for things like fatigue management. Pilots who get a medical clearance here might not get one from the FAA. These 'risks' are pretty much just accepted by the regulators as being extremely unlikely to bring down a plane in their territory given the handful of flights a week they will be making. In extreme circumstances the FAA could place some sort of condition on the approval to further mitigate the risk of differing regulations.