Regice can use Nevermeltice, Casteliacone, and Snowballs.
>Casteliacone can be found in the Trick Room at Route 110 or be bought from the little girl at the second floor of Mauville City.
>Nevermelt Ice can be found at Shoal Cave.
>Snowball can be purchased at the Battle Resort for 32BP
Source and full guide.