The way I've learned to read it that I think makes the most sense is that everyone who dies goes to the same place when seen from the perspective of the living, and it is called the Abyss/Sheol in the Old Testament. In the OT, the ideas of death, heaven/hell, eternity, etc. did not seem to cross very often.
In the New Testament (specifically in Jesus' preaching), Hades is named as the place where the godless go when they die. Sometimes it also seems to refer to the place where even believers go when they die, but again, I would expect this to be a matter of speaking from the perspective of the living.
Another place for the dead seems to be heaven/paradise (note: not the New Creation), which is named as the place where believers go when they die. Some examples of this are "Jesus answered him, 'Truly I tell you, today you will be with me in paradise' (Luke 23:43), and the place in Revelation where the martyrs are (Rev. 6:10). This seems to be the perspective of the dead. A great example of Hades being the place for the godless and heven being the place for the godly is the parable of the rich man and lazarus (Luke 16:19-31).
So that covers the spiritual resting place for the dead. The physical place for the dead is, as you saw, named a variety of ways (the grave, Hades, the sea), but they are all resurrected, so in the end, wherever each person is resting physically, they are brought back to life for judgement. At that point, those whose names are in the Book of Life become residents of the New Creation and all others will go to the lake of fire (today often called Hell). These are the eternal destinations of every man, compared to the temporary places (heaven, hades, the abyss, the grave, etc.).
I'm sure that's badly organized, but I hope it helps you clarify the distinctions between the many words that refer to the home of the dead.