Did the Golden Horde shoe their horses?

Short Answer

Generally, no. Literary evidence mostly indicates that Mongol horses were unshod, at least with metal. However, some horses' hooves were shod with skins during the time of Genghis Khan, and there is evidence that metal was sometimes used by Mongols in the west and during Kublai Khan's invasions of Japan.

Details

During the time of Genghis Khan (c. 1158 to 1227), horses were rarely shod. This from To Shoe or not to Shoe?

Genghis Khan led his cavalry to victory on barefoot horses.

Even several decades after the time of Genghis Khan, Roman Johann Jarymowycz in Cavalry from Hoof to Track notes that Mongol horses were not shod:

About the only thing that thwarted the Mongol cavalry was geography. The rock-strewn terrain of Syria initially hindered the Mongols who did not use horseshoes.

Further north, in what is now Croatia, Thomas the Archdeacon (c. 1200 to 1268) observed that Mongol horses

run around on rocks and stones without horseshoes as if they were wild goats.

Cited in Denis Sinor, 'The Inner Asian Warriors'. In 'Journal of the American Oriental Society Vol. 101, No. 2 (Apr. - Jun., 1981)'

However, at least some horses were shod, but not necessarily with iron. Rather, they used:

wet skin which was placed covering the entire hoof and allowed to dry in order to acquire the shape of the hoof. Later, Genghis Khan...perfected this technique to cover the hoof, which offered great abilities to their armies to move faster and more efficiently than their opponents.

The extent to which skins and, possibly, certain types of wood, were used is uncertain as these are perishable materials and thus whatever archaeological evidence there might have been has not survived. However, the use of skins / leather for shoeing was not uncommon in different regions of the world, and not just for horses: the Romans sometimes used Hipposandals, Arabs in North Africa shod camels and horses with camel skin, and Indian tribes in the Rocky Mountains used buffalo or elk hide.

By the time of Kublai Khan (d. 1294), though, during the Mongol invasions of Japan metal horseshoes were in use:

One of the more unusual finds in the underwater archeological excavation of Kublai Khans fleet were bricks. The Mongols built onboard forges for blacksmiths to use in making horseshoes and repairing weapons.

Also, in Armenia during the time of Hulagu Khan (c. 1215 to 1265),

According to the Armenian historian Kirakos of Gandzak, during the reign of Hulegu the very heavy taxes in kind imposed upon the conquered lands included one arrow and one horseshoe, presumably by household.

Source: Sinor

Nonetheless, this was probably not the norm but rather because there was a perceived need for a particular campaign. George Fleming, in his hefty 1869 tome Horse-shoes and Horse-shoeing, makes several references, both historical and contemporary, to the absence of shod horses among the Mongols.

Metal horseshoes had been in use elsewhere for at least a couple of centuries before the time of Genghis Khan: Leo VI of Constantinople refers to them in a treatise in 900 AD and their use may date back to 500 AD or even earlier. It is thus likely that the Mongols during the time of Genghis Khan knew about metal horseshoes, yet they did not adopt them (while they did adopt the stirrup).

There are several likely explanations for this, one being that the terrain they generally roamed was easy on horses' hooves. Also, (acknowledgement: T.E.D.'s comment for highlighting this point) the Mongols

...generally left their horses unshod, since the hooves of animals raised in a dry climate like Mongolia were harder and resisted abrasions better than horses raised in a wet climate

Jarymowycz also notes the tougher hooves of Asiatic horses compared to western ones.

Another factor is that each Mongol had several horses (between 4 and 16, depending on which source you believe); carrying the materials necessary to shoe such a large number of horses for an army on the move would have been impractical, and the constant switching of mounts prevented horses from being 'over-ridden' (the hooves of a horse with a rider are subjected to more stress).

Other sources:

Stephen Turnbull, Genghis Khan and the Mongol Conquests 1190-1400

Michael Burgan, Empire of the Mongols

The Mongol Empire’s Best Weapon: The Mongolian Horse