The Nazgûl were destroyed in the destruction of the Ring, though it is ambiguous as to whether that's because of the Ring's destruction or because they were caught in the eruption of Mount Doom. Given the eagles later make it through the eruption to rescue Frodo and Sam, I think it is reasonable to assume the former.
And into the heart of the storm, with a cry that pierced all other sounds, tearing the clouds asunder, the Nazgûl came, shooting like flaming bolts, as caught in the fiery ruin of hill and sky they crackled, withered, and went out.
This lines up with what was expected in the books:
If [the Ring] is destroyed, then he will fall; and his fall will be so low that none can foresee his arising ever again. For he will lose the best part of the strength that was native to him in his beginning, and all that was made or begun with that power will crumble
(The Return of the King)
The latter I take to include the Nazgûl, as their Rings will lose all power when the One Ring is destroyed and they are, in effect, a creation of Sauron.
As to what happened to their souls, neither of the canon sources on the demise of the Nazgûl indicate what happened to them. The above obviously offers no guidance, and when the Witch-King fell nothing was noted either:
with her last strength she drove her sword between crown and mantle, as the great shoulders bowed before her. The sword broke sparkling into many shards. The crown rolled away with a clang. Éowyn fell forward upon her fallen foe. But lo! the mantle and hauberk were empty. Shapeless they lay now on the ground, torn and tumbled; and a cry went up into the shuddering air, and faded to a shrill wailing, passing with the wind, a voice bodiless and thin that died, and was swallowed up, and was never heard again in that age of this world.
There's no explicit mention of Hell in Tolkien's mythologies nor in his Letters other than very early versions of The Silmarillion in The History of Middle-earth, generally referring to Angband, which is not really applicable in this case as that was a real place - not an underworld.