This video shows the entrance to the Shrine or Worship open in Shadow of the Colossus:
How exactly do I achieve this?
I could be wrong, but I believe the open gate is just in the demo. The video you mention says that the version of the game that s/he is showing is the demo from the Official Playstation Magazine demo disk.
In the normal game, you can reach the secret garden he mentions, but I don't know that you can open the gate to the Shrine of Worship.