Short answer: public (federal or state government) aircraft operations can be exempt - but aren't always - from most FAA regulations, provided they're non-commercial operations. Any regulation that specifically applies to a "civil aircraft" doesn't apply to a public aircraft operation.
First, some definitions from 14 CFR 1.1:
Civil aircraft means aircraft other than public aircraft.
Public aircraft means any of the following aircraft [...]
The definition of "public aircraft" basically comes down to 'any aircraft the government owns or has a long-term lease on'. That potentially covers everything from Air Force One down to the Podunk Sheriff Department's C172. With that in mind, a lot of regulations apply only to civil aircraft, e.g. 14 CFR 61.3 requires a pilot's certificate to operate an aircraft (emphasis mine):
(a) Required pilot certificate for operating a civil aircraft of the
United States. No person may serve as a required pilot flight
crewmember of a civil aircraft of the United States, unless that
person:
So 61.3 doesn't apply to public aircraft. Similarly, 91.203 requires an airworthiness certificate for civil aircraft only (emphasis mine):
[...] no person may operate a civil aircraft unless it has within it the following:
(1) An appropriate and current airworthiness certificate
As for maintenance, part 43 only applies if an aircraft has that certificate, per 43.1:
this part prescribes rules governing the maintenance, preventive maintenance, rebuilding, and alteration of any—
(1) Aircraft having a U.S. airworthiness certificate;
In other words, if your aircraft is public use then you don't need a pilot's certificate to fly it, you don't need an airworthiness certificate, and therefore you don't need maintenance! See also 91.7, 91.9 and many other regulations that only apply to "civil aircraft".
Whether or not a specific flight is a public aircraft operation (PAO) or not is explained in AC 00-1.1A, Public Aircraft Operations. Pages 10 and 11 have flowcharts for determining whether a flight is a PAO but to simplify, if the aircraft is owned by the government and the flight isn't for commercial purposes (also defined in the AC) then it's a PAO. And that means many regulations don't apply to them:
What Oversight of PAO Does the FAA Have? The FAA has limited oversight of PAO,
though such operations must continue to comply with the regulations applicable to all aircraft
operating in the NAS.
Again, if you read the regulations with the civil/public distinction in mind then you can see a lot of exemptions. For example, 91.131 is the regulation for operations in class B airspace. It says (emphasis mine):
(a) Operating rules. No person may operate an aircraft within a Class B airspace area except in compliance with §91.129 and the following rules:
(1) The operator must receive an ATC clearance from the ATC facility having jurisdiction for that area before operating an aircraft in that area.
[...]
(b) Pilot requirements. (1) No person may take off or land a civil aircraft at an airport within a Class B airspace area or operate a civil aircraft within a Class B airspace area unless—
(i) The pilot in command holds at least a private pilot certificate;
That means (a) applies to all flights but (b) applies only to civil flights, i.e. a PAO flight still needs a clearance for class B airspace, but the pilot doesn't need to have a pilot's certificate. It looks to me like the regulations are generally written so that everyone has to follow the same rules of the air (for obvious safety reasons) but public aircraft are often exempt from licensing, airworthiness and maintenance requirements.
Does this all mean that US airspace is full of unlicensed pilots flying non-airworthy aircraft that haven't been maintained properly, all under the cover of government business? Not really; the government has as much interest in safe and productive flying as anyone else, and that requires qualified pilots and well-maintained aircraft. There are some plausible reasons for the PAO exemptions, like allowing military pilots to operate civil flights, and federal and state governments are often exempt from their own legislation in all sorts of areas, not just aviation.
