I was actually thinking more along the lines of a zeppelin style airship as they appear in Stardust or that newest three musketeers movie (though without propellers or cannons). The air greyjoys could have developed a technique for enchanting the wood as it's built that makes it function as if it weighs almost nothing, and lift could be achieved by heating the air in the balloon and and harnessing the winds with magic. The specific techniques used would be their most closely guarded secret, so they'd be the only ones with reliable airships (barring those captured in battle).