I was in Arches and Canyonlands a few years back:
http://www.langfordphotography.com/Colorado-and-Utah/Arches-and-Canyonlands/6348472_Wcc3N
I'm pretty sure you will have very little to zero light pollution from the nearby town. If the moon is not up and/or full, it gets VERY DARK out there. And I mean, it's creepy dark.
The hike up to Delicate Arch is a bit of work, and coming back down in the dark could be tough. Take a good flashlight.
For lighting, you could rely upon the moon, which works very well if it is behind you and big:
I don't think strobes or anything would be practical. I would just "paint" the arch with your flashlight for a bit, which should work well for lighting it up.
Here's a shot from Isle in the Sky, which is in Canyonlands. The moon was very small and behind me, but didn't give off much light. Full moon works very well if it is behind you. I couldn't sit out on the edge of this 1000 foot cliff for very long. I ended up leaving my camera shooting, and headed back to my car.
I personally don't shoot one long exposure for star trails ever. I don't like the noise that comes along with them (at least in my camera). I "stack" my shots. Typically I'll shoot at F2.0 with my 20mm prime lens, at about 1 1/2 minutes each exposure (depending upon how bright the moon is). I use a remote that allows taking one shot after another, and the time between each shot is minimal. Also, shooting at a open aperature and short exposure will allow you to test your "painting" each checking the shot. Once you get a good painted Arch, start up your non-stop shots and sit back and relax. You are looking at 1 to 2 hours to get a good full covered sky in trails.
Anothing thing you could consider, although it is much more difficult, is setting up early and capturing a dusk shot with some color still in the sky. You have to be careful with this, as the sky can kill the star trails. It works sometimes, though:
Anyway, good luck! Can't wait to see the results.
EDIT: I use this remote:
http://www.bhphotovideo.com/c/product/164271-REG/Canon_2477A002_Timer_Remote_Controller_TC_80N3.html
The 5DMKII may have that timer functionality already built into it, I don't know.
James