First, go to Fuschia city (if you're not there already), now go to the house on the right of the Pokèmon Center. The Safari zone warden (the old man) will say he lost his teeth in the Sarfari zone. Now go to the Safari zone, in the top half (near the house you get HM surf in), you will find a Pokè ball on the floor that contains an item called Gold teeth. Finally, after the Safari zone game is over, go back to the old man's house (which should now be eastward from the Safari zone) and speak to him again, he will take the gold teeth and give you HM strength in return. There is a movable boulder in his house that has a rare candy behind it, that you now move once you teach a Pokèmon the HM strength (Geodude can learn it for example).
Hope I helped! =)