Soldato
I'm also pretty new (started last weekend!) but I've watched a lot of games online
I am beginning to find that the best way to build a deck is usually to start by taking any of the crucial must-have cards specific to the class (and not taking the ones which suck for that class) and then make sure you have an adequate amount of decent neutral 2 & 3 drops, this I guess would make up perhaps 20/30 of the cards in your deck by that point (depending on how many "good" cards that class has). Then for the final 10 cards ensure you have some decent heavy-hitters and neutrals that synergise well with the hero ability of the class and/or the class specific cards, or to fill in aspects of the deck that are missing thus-far (silence, card draw, removal)
I tend to tweak my deck after every few games if I notice that I keep getting stuck in the same situation (i.e. opponent keeps being able to get too many minions on the board and I'm stuck playing one minion at a time and not able to clear the board - might need more removal spells). But it's all obviously a bit cloudy and ad-hoc because sometimes you might have just got unlucky with the cards you drew
I would give it 10-20 games before changing unless you really are getting creamed all the time.
It is a card game and like any card game there are elements of luck thrown in.