I did this hike in May of 2007, taking most of the day, with much of that time spent looking at ruins and rock art. I walked about halfway down canyon to the junction with Grand Gulch. It is an easy day hike down to the junction of Step Canyon and Pine Canyon, or all the way to Grand Gulch, which is only a few kilometers further. Step Canyon is easily navigable down to Grand Gulch. There are a couple of small pouroffs that pose no problem. You could return by the same route, or with some walking across the mesa top if you choose. Either way it makes for an interesting and pleasant day of hiking with no obstacles or surprises along the way.
All along the route I found ruins. There were both large and small prehistoric ruins, as well as some very interesting historic ruins- a couple of cowboy camps, one with an incredible collection of artifacts to view. There were also some unique rock art panels, including Kokopelli petroglyphs.
The head of Step Canyon is accessed from Highway 95 near the turnoff to Natural Bridges National Monument. The access road is marked "Road 2301". It is found on the 1:24,000 Kane Gulch mapsheet at the benchmark BM6549. You may have to open and close a barbed wire gate just after leaving the highway. Drive on this road to the point marked "6243T" just onto the Moss Back Butte mapsheet. At this point you will be on slickrock and overlooking Step Canyon. This location makes for a good camp, out on the rim of Step Point, allowing for great views to the west and an early start the next morning.
You could use this as an entrance or exit to Grand Gulch for a longer hike.If you had two vehicles. You could park one vehicle here and enter at any number of locations including Bullet Canyon trailhead, Toadie Canyon trailhead, or even at Kane Gulch Ranger Station and do a loop backpack trip. You could enter here and exit at Government trailhead near Pollys Canyon or Collin's Canyon trailhead further down Grand Gulch.
The 1:24,000 mapsheets needed for this dayhike are Kane Gulch, Moss Back Butte, and Pollys Pasture.