There is an excellent CD of music from the first season:

Deadwood Soundtrack

The "Parental Advisory" is not for song lyrics, but for snippets of dialog from the show added between songs.