To revisit this topic...
It would be as simple as a checkbox in each deck for public or private. If public, a player could see list of the public decks in the other player's profile, then click in it to display the deck.
We already have the Import/Export functions for the decks that I doubt anyone uses (I know Fithz did at some point), which we could use to send information back and forth between players.
To prevent abuse, maybe not allow a player to look at another player's deck that he is currently playing against.
Thoughts?