Wife and I mad the same trip for our honeymoon.
If you have a chance stop and see "newspaper rock" it's a petroglyph with some freaky carvings.
That place is awesome, well worth it. Very cool history there.
Lots of great advice in here, I love that part of the country. I highly recommend renting a SXS for a day in Moab. If you go to Arches or Canyonlands, do it early morning when the park opens. Herds of zombie tourists start filling the place up and people suck. My favorite arches are way out of most people's reach and require a 4WD to get to. They are the best because you rarely ever see another person at them.