The Decemberists have alot of pirate/seafaring themed songs. Alot of the imagery Meloy uses in his songwriting is very old world, traveler type stuff, along with other themes that are bound to older times and storytelling styles. The music itself is influenced by that sort of by-the-docks sound, with accordians, dramatic production, and Meloy's voice, which can sound like a very enthusiastic storyteller.
See:
"A Cautionary Song" - about a woman whoring herself out to sailors to take care of her children.
"Shanty For The Arethusa" - about the sailing life.
"We Both Go Down Together" - about two star-crossed lovers belonging to different classes.
"For My Own True Love (Lost At Sea)" - explanatory.
"The Mariner's Revenge Song" - a son gets revenge on the man who used his mother and then left her with nothing. involves getting swallowed by a whale at sea.
The Decemeberists' EP, The Tain, is based on an 8th Century Celtic poem called "Tain Bo Cuailinge".
So... the Decemberists aren't necessarily completely "pirate-rock", but much more "literary-rock", which can include things like pirates.