If you already reached that part in SoulSilver, this means you already have access to HM Surf. Here are some possibilities.
You don't have a Pokemon in your Party that knows Surf.
Even if you have a Pokemon in your Party that learns Surf, it may be because you went to the move deleter and deleted it.
You didn't press the A Button while facing the water even if you have a Pokemon that have Surf as a move.
You didn't click your Pokemon that knows Surf in your Party and selecting the Surf option. (What Indigo said in the comments)
You don't have the Gym Badge that allows you to Surf and you may have cheated all the way to where you are currently.
You don't have the HM Surf. You may have skipped the part where an old man gives you Surf after beating he Rocket Grunt in Ecruteak City dance theater. Like I said before, you cheated all the way without having Surf.
There may be just a small glitch. Maybe if you reset your game, it will work.
You should provide more information about your game and whether you are playing on an Emulator or DS. I will try to edit the anwser to a better one to help you.
This is what the game will say when you press A facing the water having a Pokemon that learns Surf and having the Gym Badge.
The water is a deep blue...
Would you like to surf on it?
Source : Testing out myself on my game.
