Actually, no, not automatically. They're considered "Public Aircraft Operations" and many aspects of the FARs don't apply to them. See Advisory Circular AC No: 00-1.1B. The military often implements aspects of the FARs into their own regs, though.
Also, 14CFR 91.117 has the magic words, "Unless otherwise authorized by the administrator." We had a Presidential TFR over Seattle about ten or so years back; somebody in a Cessna came wandering down from the north and the sicced two F-15s on him (the Cessna, not the President). The Eagles flew over Seattle at over Mach 1; nearly knocked me out of my chair at work. You can bet the pilots weren't charged with FAR violations. In fact, the prohibition against sonic booms (14CFR 91.918) specifically excludes military aircraft...but they still were above 250 knots.
Ron Wanttaja