To get the HM Surf you need to speak to Darren in the middle of Kanto Safari in Fuchsia City. You need a ticket to get to the safari and it cost 20,000. From when you enter the safari go straight down and you will see a little island with a small walk way with the npc Darren standing there.
Surf lets you move across water tiles. You do NOT need to teach it to a pokémon in order to use it, however you DO need the soul badge.