I have seen this Pokemon perform well in Doubles. Especially when a gimmick or three is introduced.
In general, great moves for Palossand are Giga Drain (for Water types, healing, and coverage), Shadow Ball (STAB), Earth Power (STAB), and Shore Up. If you're not running Sandstorm, use Water Compaction; otherwise Sand Veil. Natures that take Attack or Speed in favor of Sp.Atk, Sp.Def, or Defense are essential. The three main items I have considered for this Pokemon are Brightpowder (great in combination with Sand Veil), Weakness Policy (5 weaknesses to activate it), and Assault Vest (raises your lower Sp.Def, but you can't run Shore Up with this...).
Other moves you can consider are Double Team and Stockpile (stall), Hidden Power Ice (perfect coverage with Grass, Ground, and Ghost; hits Flyers and Levitators, demolishes the most common Dragons), Toxic (Stockpile Shore Up stall), Infestation (same as Toxic), Energy Ball (more damage for less healing), Sludge Bomb (for Grass types and Fairies if you don't run HP Ice), and Psychic (wouldn't recommend).
-----------------------------------------------
First off, since this is a slow Pokemon, Trick Room partners is essential.
For this set, I'd recommend running Protect (for that turn to set Trick Room) and -Speed Natures.
Second, since Water Compaction is only good when 1) you can survive the Water attacks and 2) have a means of beating them afterward, Sand Veil is usually the preferred Ability, requiring either a Pokemon with Sand Force or one with Sandstorm (which Palossand can bring).
I have once used a level 1 Smeargle with Trick Room and Water Shuriken to pull this combo off, but it's not very consistent. Also, Palossand with Weakness Policy and Giga Drain can revenge kill several Water types.
Third, to increase this Pokemon's bulk, a Simple Beam user can maximize Palossand's defenses through Stockpile. Combining that with Weakness Policy and Double Team, and you'll have +4 offenses and +6 Defenses AND Evasion!
Protect prevents Simple Beam from affecting you, so it might not be best to run it; but using it on a Trick Room turn can be beneficial. Allies that have Trick Room and Simple Beam can also run Heal Pulse if you don't use Shore Up that turn (Audino only), Ally Switch to confuse opponents (Natu and Elgyem's lines), Fling's Rock (Audino, Grumpig, and Inkay's line), Sandstorm (unfortunately, only Smeargle) U-Turn into a Sandstorm/Sand Force (only Natu's Line)... Or just switch out for a Sandstorm/Sand Force Pokemon.
Of the possible Simple Beam sets, the strongest I ever considered held Leftovers or Leppa Berry and ran Stockpile, Shore Up, Double Team, and Infestation next to Sandstorm setters and/or a Corrosion Toxic/Poison Gas Salazzle. Unfortunately, self-sustaining Pokemon, as well as those with no-Miss/bypass accuracy moves and abilities (like Toxic on Poison-types, Smart Strike Kartana, No Guard Doublade, Darkest Lariat Incineroar...) will run this into the ground. Especially Incineroar, since Darkest Lariat is super effective and ignores both the Defense boosts AND the evasion boosts.
