Are you going to be riding there or just hanging out/hiking? We went there from NC in 2006 and did a lot of hiking in Arches and Canyonlands. No problems whatsoever. We had trained for hiking but did nothing specific for altitude and took no meds. I don't think the altitutde there should be a problem since it's really not that high. Honestly, we never even thought of doing anything to prepare or take any meds...not sure if it's worse if you're cycling vs. the long hikes we did.

Good luck!