You have a few routes to take.

The first is to purchase the welcome bundle. ($10). You get a guaranteed class legendary, and there's a considerable possibility that you're going to get a good one. Even if it's a less than great one like King Krush, it's still going to be a better card than what you have now.

The second is to open a Whispers of the Old Gods card pack. Doing this will give you a free legendary card (C'thun). C'thun exists almost solely as a way for new players to be able to have a decent legendary to build a starter deck around. He amasses attack and health when you play other certain Whispers of the Old Gods cards, including the two Beckoner of Evil cards that you'll also be given alongside C'thun. Their card text reads "Give your C'Thun +2/+2 (Wherever it is) - meaning that whether C'Thun is in play, in your hand, or in your deck it will be buffed. When you play C'Thun, it unleashing all of its attack points immediately, at random, to enemy targets. All C'Thun cards simply buff C'Thun in some way.

It's an easy, good, fun deck to make and it works reasonably well with whatever class you want to use him with. Each class also has their own unique C'Thun related card. If you build the deck well, you can definitely win matches and feel like you're playing a real deck instead of the usual boring, beginner "Play Vanilla cards on curve and hope it's good enough" kind of thing. It's not exactly the greatest deck archetype at the moment, but it's functional for a beginner and can likely bring you to rank 15 with enough practice.

The other option is to spend even more money in addition to the welcome bundle so you can get a jump start on working your way towards building some of the cheaper meta-decks. Pirate Warrior is likely the best option in that regard.