Becky and I just got back from a trip through some of the NPS administered lands in Southern Utah. We camped our way from Arches to Zion. One of the really great things was being able to see the stars so clearly at night. Of the parks we visited, Natural Bridges and Bryce Canyon had the darkest night skies.
You can see more photos of the night sky on flickr.