Simple.
When you enter the Desert go straight up and exit through that path. Then head right and you should enter a narrow path with a bush in the center and an old man. Head up and you should enter a giant area with an area of rocks that must be crossed while riding mudsdale. Once there head right and go through that path which should take you to a dead end. At the end of the dead end there you will find you Z-Crystal.
Source: My official guide book
