Is this normal?
The answer is no, it's not normal. If two people work on some research together, the "normal" thing is for them to write the paper on it together, and for both to be authors on the paper.
It's possible that you seriously overestimated your contribution to the work and don't actually deserve authorship. Even in this case, it's clear you were involved in the research and it's not normal for your advisor to go ahead and publish it without discussing it with you first.
(When I publish work that involves students whose small contributions do not warrant authorship, I always discuss it with them first. I explain why I don't think they can be an author, give them a chance to state any disagreement, and also tell them what additional work they could do in order to merit authorship.)
However, the latter (your contributions did not merit authorship, and your advisor failed to discuss this with you) is somewhat more forgivable than the former (your contributions did merit authorship and your advisor published without you anyways). (You do say your advisor is new, and probably inexperienced in advising.)
What do I do?
You should talk to your advisor. This is the only way to really understand which case you are dealing with.
You can bring this up in a non-combative way without upsetting your advisor; for example, you can ask "What do I need to do in order to deserve authorship on future papers?" This gives your advisor an opening to discuss why he thinks you didn't deserve authorship on the conference paper, and for you to respectfully state your perception of the situation.
There may still be a chance for you to get some credit for this work, if you come to agree with his point of view that you didn't do enough to deserve authorship on the conference paper. For example, once you and your advisor have come to an agreement on what it takes to get authorship, you can propose that the two of you work together on an extended version of his conference paper for a journal - on which you will be an author :)
Unfortunately, it's also possible that after this conversation you believe you did deserve authorship, and that your advisor published your joint work without you for no valid reason (i.e., committed misconduct). In this case, the best advice I can give you is to start looking for another advisor.
Finally, the lesson for the future is: talk to your collaborators about authorship early and often.