Battlegrounds->Training PVP Game->Click on the deck you want, there should be either a gold price or instructions on how to unlock that deck
This confused me too. I kept reading in guides that you could purchase more public decks for 1000 gold, but they weren't in the Marketplace under the Decks heading, so I assumed at first that they were no longer available. It's better now that playing a Training PVP game is part of the NUX, but it could still use some improvement.