Pokémon X and Y Walkthrough, Pokémon Move Sets: Malamar
(Please note that the recommendations below are largely made for in-game play. A Malamar in a competitive environment will likely make use of different moves to accommodate for smarter, more adaptive opponents. If you have some alternate Malamar strategies, toss 'em out for us in the comments.)
An upside-down squid that lives on land and unites two move types that are normally mortal enemies? What a strange and wonderful thing this Malamar is. Unfortunately, the reality is not nearly so cool as the hype, and though Malamar is stytlistically neat it doesn't work so well in practice. Nevertheless, it's quite possible to turn a Malamar into a functioning part of your team.
Type: Dark / Psychic
Malamar's a weird one. It evolves from Inkay at level 30, which in and of itself isn't that strange - except that you have to hold your 2/3DS upside down to make it evolve. Fail to do that and your Inkay will simply level. Turn your handheld upside down as soon as you receive notification of leveling (as well as end the battle) and you'll get your Malamar.
None. Immune to Psychic.
Bug (4x), Fairy.
For all its potential, Malamar is really let down by its stat spread. It looks decent enough on paper - HP is okay, Attack is a bit above average, Defense is decent, Special Attack and Special Defense are eh, Speed is about the same - but Malamar barely gets a boost from its Inkay roots. Its lack of resistances make it really easy to kill - though on the plus side, it is quite good at bringing down psychic-types, so long as they aren't sporting X-Scissor or Signal Beam.
Contrary: Stat changes to the pokémon are reversed. Negative changes are made positive; positive changes are made negative. This sounds horrible, but Malamar has the benefit of knowing Superpower, an incredibly-strong move which, under the influence of Contrary, boosts Malamar's Attack and Defense. This ability is the primary reason to give Malamar a try in the first place.
Suction Cups: The pokémon cannot be removed from battle by the enemy. This is good for countering Roar, but it can't hold a candle to Contrary.
Infiltrator: The pokemon's attacks ignore enemy barriers, including Reflect, Light Screen, Safeguard, Mist, and Substitute. This is a really neat ability, but in the long run it's quite situational. In many cases, particularly during the main game, it won't come into play very often.
Malamar can fill a few roles, though most players will probably want to try it out with Superpower. So long as you have Contrary active, Superpower can give your Malamar some nice boosts while dishing out solid damage against the enemy. Foul Play is a good STAB addition to Malamar's repertoire, as is Psycho Cut. I also recommend Hypnosis, because, well, everybody loves Hypnosis.
The alternative is turning Malamar into a debuffer of sorts. Topsy Turvey reverses any stat changes to an enemy pokémon; Switcheroo swaps items. The latter is particularly fun if you give Malamar a Toxic Orb and then foist it off on an enemy you couldn't normally take down. Toss in Hypnosis and a STAB move / Superpower to finish off the moveset. You can also substitute in Reflect and / or Light Screen to turn Malamar into a part-time buffer for your team.
EV / Super Training
This depends on your angle. An attacking Malamar really needs to emphasize that Attack stat, so train accordingly. Make the most of Superpower by completely ignoring Special Attack. Conversely, a Malamar that debuffs will probably want higher defensive stats; put more effort into Special Defense. In either case, you'll want to max out Malamar's Speed - it often won't be able to outpace enemy pokémon, and if that happens Malamar's usually toast.
Catching a Malamar
Catching a Malamar necessitates catching an Inkay. Despite how it looks, you can find Inkay relatively often in Route 8's grassy patches, far from the water. Once it's caught, level it up to 30 and pull the ol' switcheroo when it hits 30 to get your Malamar. (That said, I suggest breeding a level one Inkay so you can make the most of EV training. Seriously, this thing needs EV training. Can you tell I'm a little disappointed with Malamar?)