Battle Moveset

A Good Moveset for Walrein would have to be this:

Attacks:

Encore
Ice Beam
Hidden Power Psychic
Surf

Items Attached:

Leftovers

Preferred Nature:

Modest

Strategy Using Walrein

Walrein has good stats in all but speed. The reason I picked Modest as its nature was due to it needing a boost in special attack, the other choice was Timid but this wouldn't help out the pokemon since it already has below average speed.
I would like to point out that its ability isn't that good, I doubt you'll see anybody use a fire or ice attack on a Walrein. Maxed out EV's in Special attack to boost the three moves: Surf, Ice beam, HP Psychic. EV's into HP and Defense will help it last longer. The move Encore can prove useful if your opponent uses a move that is designed to boost stats, giving you time to launch attacks.
You can consider replacing Encore with Yawn to put your opponent's pokemon asleep. Surf and Ice beam, both get extra strength from STAB and are also excellent sweeping moves. HP Psychic is something you don't see that often but will prove useful in most battles.
Its a shame this pokemon is considered under-used, it has loads of potential and should be considered in any team.

EV Corner:

Max out the EVs in Special Attack for Walrein with any remaining in Hit Points & Defense

Strategy Against Walrein

Walrein has equally high defenses causing this Pokémon to be very hard to beat. So what you should do here is get it with it's weaknesses; Fighting, Rock, Grass & Electric will do good here

Contest Moveset

A good Contest Moveset for Walrein would have to be this for theBeauty Contest best with Modest, Mild, Rash or Quiet Nature:

Attacks:

Ice Beam
Hail
Rain Dance
Surf

Items Attached:

Blue Scarf

Strategy Using Walrein

If you do the attacks in this following order you should have very few problems; 1st - Hail, 2nd - Ice beam, 3rd - Rain dance, 4th - Surf, 5th - Ice beam

Locations in Games

Ruby/Sapphire Evolve Sealeo Colosseum Trade From R/S Fire Red/Leaf Green Trade From R/S

Animé Appearences

Walrein has had an Animé Appearences. Team Aqua used it in their battle against Team Magma on top of Mt. Chimney so they could get the Meteorite Episode 330: Once Again, Team Magma VS. Team Aqua! Mt. Chimney Battle!