It is in Twist Mountain. Unfortunatly, many items in Twist Mountain can only be obtained in Winter, including Substitute, so go back to Twist Mountain then. The TM is rather easy to get. If you go outside where all the snow is, there are a few new cavern entrances. Go in one in the top left on the area. You will come to a maze like area. Next to the trainer after entering, you will see an item to the left. This is Substitute. Go foward and then right, beat the trainer, go down the steps and get your TM!
While your there, through another entrance at the top left, there is a "path" with a guy facing the wall. Talk to him, and he will give you A Pokemon Fossil which you can turn into a Pokemon at the Nacrene City Museum/Gym.