Some non-federal governmental entities managed to get .gov domains before the restrictions were tightened (similar to the situation with .edu), and they were "grandfathered in" and allowed to keep them. For instance, the state of Washington has its site at wa.gov.
However, in more recent times, the restrictions were loosened again, and state and local governments in the United States may obtain new .gov domains once again.
The tightened restrictions supposedly only allowed entities at the top level of the federal government's organization chart to have separate .gov domains (subsidiary agencies were supposed to use subdomains of their parent), but this seemed to be getting considerably loosened in practice more recently, as all sorts of "vanity" .gov domains, like americaslibrary.gov, have been issued. This isn't such a bad thing, if the availability of vanity domains in .gov can at least sometimes restrain the governmental types from abusing the domain name system even worse by getting inappropriate vanity domains in .com, which is really stupid given that they're not commercial entities, but they're doing a lot of it anyway.
Properly, however, U.S. government entities ought to be in the .us country code domain, just as governments of other countries are in their appropriate country codes (at least when they're not abusing the system and getting dumbass .com domains too). It's just a historical accident that they wound up in .gov and .mil. The .fed.us domain exists for the use of Federal agencies wishing to be more properly structured in this way.