I'll start with a disclaimer: Although I haven't mountain biked much in the Moab/Canyonlands/Arches area, I've visited it a number of times for 4x4 trips when we lived in CT. We now live about 4 hours north in SLC. We've done the major trips of the White Rim, Needles, and Maze as well as some others. We've seen a fair bit of ruins and pictograph panels.
With that said, the key thing to remember (and not take lightly) about any of the organized/guided trips is that they come with 4x4 support. The distances are vast and, for the most part, there is no water available. The White Rim is approx. 125 miles pavement to pavement (and if you want to do it as a loop back to your starting point, a 2000 foot climb out is required). On our Maze trip we drove about 150 miles over 3.5 days. The guides also know where there is good riding on a given trip and which areas should be avoided.
For example, in the Maze district, in the Standing Rocks area, is a good 5 - 10 miles of deep (for a mtn. bike) sand, making a miserable riding experience. The point is just knowing which trails the organized trips take isn't quite the whole story.
The Kibab Tours site Dizzy mentioned really doesn't give a whole lot of info about where they go. For instance, they talk about seeing pictographs on the Maze trip and specifically mention the Harvest Scene (spectacular, btw). However it's not on most maps, a bit of a hike from one of the campsites, and requires some pretty good map reading skills (plus some guesswork).
If you want specific info about where to find ruins and pictographs, let me know - I'd rather not post them in a public forum - so many have suffered so much vandalism over the years.
One site that has pretty good info and trail suggestions/maps is: http://www.utahmountainbiking.com/trails/