The arch used in 'Once Upon a Time..' was originally built just outside Monument Valley, Utah, on a plateau along highway 163. It was a wooden structure, clad with brick that stood overlooking Monument valley for decades until the top fell down in the 90's. All that's left now are the two supports that used to hold up the round top.
When one leaves Monument Valley at Gouldings or Visitor Center / View Hotel and then turn northwards to Mexican Hat (or 'Sombrero' as I think this town should have been called ;D) after a few miles you will come to the point where the road goes up a plateau. This is also the famous photo-spot facing south where you have this long straight road with the mittens in the back. After that, a dirt road exits the 163 on your left and goes up the plateau. Follow that dirt road until you come to a crossing. Just follow the main road to the left until you get to an airfield site, where you follow the road to the right. Go all the way past the (hardly recognizable) airstrip and you will end up right in front of the remains of the arch.. Can't miss it!
Additionally, here are some shots from the Rio Arlanza area in Northern Spain, where the finale for Good, Bad, Ugly was filmed. You GOT to love the cemetary location!