It is LEGAL to carry a firearm in any state park, state wildlife management area (WMA), state & national wildlife areas and refuges, national forests, and national parks. This applies to everyone who has a valid concealed firearm permit AND Constitutional Carry for anyone at least 21 years old (residents and non-residents) if you are not a prohibited person as defined in 76-10-503 or 18 U.S.C. 922(g). Keep in mind that National Forests, National Parks, and National Wildlife Areas & Refuges are in more than one state, the laws governing firearms may change depending on your location within that location.

It is ILLEGAL to carry a firearm in any buildings owned by the federal government on any state park, national forest, or national park.
This includes, but not limited to, government offices, visitor centers, ranger stations, fee collection buildings, and maintenance facilities. All federal buildings must be posted or you must be informed they are a federal building. See 18 USC Sec. 930 below.

Note: Restrooms and picnic shelters that are free-standing and not part of another building should not be considered a federal building.

Laws

Utah Laws

76-10-508. Discharge of firearm from a vehicle, near a highway, or in direction of specified items -- Penalties.
(1) (a) An individual may not discharge a dangerous weapon or firearm:
(i) from an automobile or other vehicle;
(ii) from, upon, or across a highway;
(iii) at a road sign placed upon any highways of the state;
(iv) at any communications equipment or property of public utilities including facilities, lines, poles, or devices of transmission or distribution;
(v) at railroad equipment or facilities including a sign or signal;
(vi) within a Utah State Park building, designated camp or picnic sites, overlooks, golf courses, boat ramps, and developed beaches; or
(vii) without written permission to discharge the dangerous weapon from the owner or person in charge of the property within 600 feet of:
(A) a house, dwelling, or any other building; or
(B) any structure in which a domestic animal is kept or fed, including a barn, poultry yard, corral, feeding pen, or stockyard.
(b) It is a defense to any charge for violating this section that the person being accused had actual permission of the owner or person in charge of the property at the time in question.
(2) A violation of any provision of Subsection (1) is a class B misdemeanor.
(3) In addition to any other penalties, the court shall:
(a) notify the Driver License Division of the conviction for purposes of any revocation, denial, suspension, or disqualification of a driver license under Subsection 53-3-220(1)(a)(xi); and
(b) specify in court at the time of sentencing the length of the revocation under Subsection 53-3-225(1)(c).
(4) This section does not apply to a person who:
(a) discharges a firearm when that individual is in lawful defense of self or others;
(b) is performing official duties as provided in Section 23A-5-202 and Subsections 76-10-523(1)(a) through (f) and as otherwise provided by law; or
(c) discharges a dangerous weapon or firearm from an automobile or other vehicle, if:
(i) the discharge occurs at a firing range or training ground;
(ii) at no time after the discharge does the projectile that is discharged cross over or stop at a location other than within the boundaries of the firing range or training ground described in Subsection (4)(c)(i);
(iii) the discharge is made as practice or training for a lawful purpose;
(iv) the discharge and the location, time, and manner of the discharge are approved by the owner or operator of the firing range or training ground before the discharge; and
(v) the discharge is not made in violation of Subsection (1).

Federal Laws

National Forests / National Parks / State & National Wildlife Areas & Refuges:
National Park System on Firearms
National Monuments, National Preserves, National Historic Sites/Parks, National Rivers, National Memorials, National Recreation Areas, and National Seashores all fall under the National Park Service which the Department of Interior operates.
Congress approved a new law allowing loaded firearms in national parks starting Feb. 22, 2010. That means people can openly carry legal handguns, rifles, shotguns, and other firearms and also may carry concealed guns as allowed by state statute. The new federal law applies state law to the possession of guns in national parks. Because some national parks are in more than one state, the laws governing firearms may change depending on your location within that park.

It is your responsibility to understand individual state laws and to know which state you are in when in a multistate national park.

36 CFR 261.1b - Penalty.
Section 2.4 Weapons, traps and nets.
(a)(1) Except as otherwise provided in this section and parts 7 (special regulations) and 13 (Alaska regulations), the following are prohibited:
(i) Possessing a weapon, trap or net
(ii) Carrying a weapon, trap or net
(iii) Using a weapon, trap or net
(2) Weapons, traps or nets may be carried, possessed or used:
(i) At designated times and locations in park areas where:
(A) The taking of wildlife is authorized by law in accordance with § 2.2 of this chapter;
(B) The taking of fish is authorized by law in accordance with § 2.3 of this part.
(ii) When used for target practice at designated times and at facilities or locations designed and constructed specifically for this purpose and designated pursuant to special regulations.
(iii) Within a residential dwelling. For purposes of this subparagraph only, the term ‘‘residential dwelling’’ means a fixed housing structure which is either the principal residence of its occupants, or is occupied on a regular and recurring basis by its occupants as an alternate residence or vacation home.
(3) Traps, nets and unloaded weapons may be possessed within a temporary lodging or mechanical mode of conveyance when such implements are rendered temporarily inoperable or are packed, cased or stored in a manner that will prevent their ready use.
(b) Carrying or possessing a loaded weapon in a motor vehicle, vessel or other mode of transportation is prohibited, except that carrying or possessing a loaded weapon in a vessel is allowed when such vessel is not being propelled by machinery and is used as a shooting platform in accordance with Federal and State law.
(c) The use of a weapon, trap or net in a manner that endangers persons or property is prohibited.
(d) The superintendent may issue a permit to carry or possess a weapon, trap or net under the following circumstances:
(1) When necessary to support research activities conducted in accordance with § 2.5.
(2) To carry firearms for persons in charge of pack trains or saddle horses for emergency use.
(3) For employees, agents or cooperating officials in the performance of their official duties.
(4) To provide access to otherwise inaccessible lands or waters contiguous to a park area when other means of access are otherwise impracticable or impossible. Violation of the terms and conditions of a permit issued pursuant to this paragraph is prohibited and may result in the suspension or revocation of the permit.
(e) Authorized Federal, State and local law enforcement officers may carry firearms in the performance of their official duties.
(f) The carrying or possessing of a weapon, trap or net in violation of applicable Federal and State laws is prohibited.
(g) The regulations contained in this section apply, regardless of land ownership, on all lands and waters within a park area that are under the legislative jurisdiction of the United States.
(h) Notwithstanding any other provision in this Chapter, a person may possess, carry, and transport concealed, loaded, and operable firearms within a national park area in accordance with the laws of the state in which the national park area, or that portion thereof, is located, except as otherwise prohibited by applicable Federal law.

36 CFR 261.10 – Occupancy and use.
The following are prohibited:
(d) Discharging a firearm or any other implement capable of taking human life, causing injury, or damaging property as follows:
(1)  In or within 150 yards of a residence, building, campsite, developed recreation site or occupied area, or
(2)  Across or on a National Forest System road or a body of water adjacent thereto, or in any manner or place whereby any person or property is exposed to injury or damage as a result in such discharge.
(3)  Into or within any cave.

“Cave means any naturally occurring void, cavity, recess, or system of interconnected passages beneath the surface of the earth or within a cliff or ledge and which is large enough to permit a person to enter, whether the entrance is excavated or naturally formed. Such term shall include any natural pit, sinkhole, or other opening which is an extensive of a cave entrance or which is an integral part of the cave.”

Forest Service regulations require that you also comply with all State laws regarding the use of firearms while hunting.
If you are planning on visiting a designated Wilderness Area, the Regional Forester or Forest Supervisor has the option to implement a special local order which additionally prohibits the mere possession of a firearm within that Wilderness Area.

Contact the Forest Supervisor’s office to find out whether such a restriction has been imposed.
Be advised that any Ranger Station or Visitors Center run by a federal agency in any National Forest or Wilderness Area is considered a Federal Building. It is illegal to carry any firearm into such a building either concealed or openly even with a concealed firearm permit from the state of the National Forest Ranger Station or Visitors Center. By Federal Law if it is Off Limits to Firearms it must be posted.

50 CFR 27.42 Firearms.
(e) Notwithstanding any other provision in this Chapter, persons may possess, carry, and transport concealed, loaded, and operable firearms within a national wildlife refuge in accordance with the laws of the state in which the wildlife refuge, or that portion thereof, is located, except as otherwise prohibited by applicable federal law.

18 Sec. 930. Possession of Firearms and Dangerous Weapons in Federal Facilities
(a) Except as provided in subsection (d), whoever knowingly possesses or causes to be present a firearm or other dangerous weapon in a Federal facility (other than a Federal court facility), or attempts to do so, shall be fined under this title or imprisoned not more than 1 year, or both.
(b) Whoever, with intent that a firearm or other dangerous weapon be used in the commission of a crime, knowingly possesses or causes to be present such firearm or dangerous weapon in a Federal facility, or attempts to do so, shall be fined under this title or imprisoned not more than 5 years, or both.
(c) A person who kills any person in the course of a violation of subsection (a) or (b), or in the course of an attack on a Federal facility involving the use of a firearm or other dangerous weapon, or attempts or conspires to do such an act, shall be punished as provided in sections 1111, 1112, 1113, and 1117.
(d) Subsection (a) shall not apply to –
(1) the lawful performance of official duties by an officer, agent, or employee of the United States, a State, or a political subdivision thereof, who is authorized by law to engage in or supervise the prevention, detection, investigation, or prosecution of any violation of law;
(2) the possession of a firearm or other dangerous weapon by a Federal official or a member of the Armed Forces if such possession is authorized by law; or
(3) the lawful carrying of firearms or other dangerous weapons in a Federal facility incident to hunting or other lawful purposes.
(e)(1) Except as provided in paragraph (2), whoever knowingly possesses or causes to be present a firearm in a Federal court facility, or attempts to do so, shall be fined under this title, imprisoned not more than 2 years, or both.
(2) Paragraph (1) shall not apply to conduct which is described in paragraph (1) or (2) of subsection (d).
(f) Nothing in this section limits the power of a court of the United States to punish for contempt or to promulgate rules or orders regulating, restricting, or prohibiting the possession of weapons within any building housing such court or any of its proceedings, or upon any grounds appurtenant to such building.
(g) As used in this section:
(1) The term “Federal facility” means a building or part thereof owned or leased by the Federal Government, where Federal employees are regularly present for the purpose of performing their official duties.
(2) The term “dangerous weapon” means a weapon, device, instrument, material, or substance, animate or inanimate, that is used for, or is readily capable of, causing death or serious bodily injury, except that such term does not include a pocket knife with a blade of less than 2 1/2 inches in length.
(3) The term “Federal court facility” means the courtroom, judges’ chambers, witness rooms, jury deliberation rooms, attorney conference rooms, prisoner holding cells, offices of the court clerks, the United States attorney, and the United States marshal, probation and parole offices, and adjoining corridors of any court of the United States.
(h) Notice of the provisions of subsections (a) and (b) shall be posted conspicuously at each public entrance to each Federal facility, and notice of subsection
(e) shall be posted conspicuously at each public entrance to each Federal court facility, and no person shall be convicted of an offense under subsection (a) or (e) with respect to a Federal facility if such notice is not so posted at such facility, unless such person had actual notice of subsection (a) or (e), as the case may be.