Gyarados has the ability to easily switch into battle and force the opponent to switch out. This set takes advantage of both factors in order to set up. On the turn the opponent switches to its appropriate counter, Gyarados will use Substitute. Depending on the counter, Gyarados will either Dragon Dance or Substitute accordingly, and proceed to sweep with a huge advantage in Speed and Attack. It might seem like the ease by which this is done is being oversimplified; however, this cannot be farther from the truth. How does nearly every individual deal with Gyarados? By switching, which gives Gyarados the opportunity to set up its Substitute.
For example, if the opponent switched in Starmie, Gyarados will Substitute down to Liechi activation and Dragon Dance on the final Substitute breaking turn, giving Gyarados +2 Attack, +1 Speed and a 200 BP move to easily OHKO Starmie with. However, if something like Celebi was switched in the turn Gyarados used Substitute, Gyarados will then Dragon Dance, and use Substitute if it feels a Thunder Wave / Leech Seed coming or Dragon Dance if a Grass Knot is coming. Depending on the amount of health left, Gyarados will then (probably) Substitute again for the Berry activation, and have +3 Attack, +2 Speed and 200 BP move to deal with the opposition.
Liechi Berry or Salac Berry is purely a matter of preference in the end. It depends on whether having Gyarados outspeed Choice Scarf Gengar that switch in later or having the extra boost of Attack is preferred, mostly to OHKO threats like Celebi.
Rain Dance support is a decent option to consider since the set is crippled by the effects of Hail and Sandstream.