Wyoming is a true mountain state, with the Rocky Mountains, glaciers, but also badlands and deserts. And of course the Yellowstone National Park. The main hiking area is the northwest.
Yellowstone is famous, but try to avoid the tourist traps. Better to choose the trails in the outer parts of the park. Another hit is the Grand Teton National Park, and the adjacent National Forest with the same name. The Bridger-Teton National Forest has large wilderness areas. And finally the glacier rich Shoshone National Forest. These parks count for more than 6000 miles of hiking trails.
Wyoming has its share of the famous Continental Divide Trail, and also of the Great Western Trail. The place to be!