The black coloring induced by Haki was only introduced after the timeskip. Before that, when Haki is used, it is not visible with two exceptions: Garp's punch at Enies Lobby and Whitebeard's fist at Marineford.
For example, in chapter 512, Rayleigh faces Kizaru in a sword duel. Rayleigh is using a simple sword while the admiral is wielding an energy sword made of pure light. In this fight, for Rayleigh's sword to be effective against Kizaru, he is obviously using Haki, even if the Haki is not visible at all. This is confirmed by the fact that Rayleigh's sword swing injures Kizaru, a logia user.
Therefore, Shanks' sword is not "made" of anything special (i.e. seastone), he was simply embedding it with Haki. He may be wielding one of the world's great swords but this has yet to be confirmed.