You find TM for Ice beam at the old abandoned ship in the ocean (in a storage room) but you can also get it for 4,000 Game Corner coins at the Mauville City Casino.
You also get Flamethrower for 4,000 coins at the Game Corner.
After you beat Norman, go back to Mauville and Wattson will ask you to shut off the generator in the New Mauville Power Plant. He will give you Thunderbolt as a thank-you.
Sources: Thunderbolt Flamethrower Ice Beam