I play a lot of HS these days. (Well, am on a break till Wednesday, but whatever). I am playing Constructed mainly at this point but I had a long streak of arena only.
Overall opinion is that it is quite simplified and fast, it cannot compare at all with MTG or the likes, but, damn, it is TOO MUCH FUN.
@Kirian - It's not really a "draft" format, but whatevers

I am not the best arena player ever (when I was focusing on it, my average was 6-3, but am much worse lately), but I can give some pointers. I used these when starting:
http://us.battle.net/hearthstone/en/forum/topic/9742094161 and
https://docs.google.com/spreadsheet/ccc?key=0AvFHvRgCHF4RdG16dlFNdUI1UXhhWk0yS1lITW82cnc#gid=1So, Arena is quite easy. Legendaries help (esp when a guy dropped me 3 Tirions) but generally do not matter that much (I mean, of course they are powerful but it does't matter a lot if you get them or not, generally when you analyse limited formats, commons/uncommons are the things that matter the most, as you see the most of them).
There are few things you need to know when actually picking cards. Narrow cards always suck (Sacrifical Pact, Murlock Tribals). Cards that give no board advantage generally suck (Charge, Holy Light, Eye for an Eye, Mind Blast), 1HP guys always suck (Magma Raider, Dust Devil). What you actually want:
0. Class Specific - each class has a few very strong cards that you always want. Wont list them all, most are just the top cards in respective classes in the links that I gave.
a. Bombs - big, meaty, hard hitting creatures that need to be dealt with or they win the game very fast. They have a huge board presence, are a huge threat and usually trade 2 for 1 or better. Most Legendaries, Venture Co., Stormwind, Boulderfist, Sunwalker.
b. Removal -Any card that kills a creature. Includes Weapons, and weapons are almost always best picks, in general. Class specific.
c. Effective creatures - They need to have relevant abilities and good stats, or just supreme stats. Disruption (Spellbreaker, Ooze that kills weapons), Sudden stat boost (Shattered Sun Cleric, Dark Iron Dwarf), hard to remove taunt guys (Senjin Shieldmaster, Sunwalker, Defender of Argus in a sense), "two for one" guys (Argent Commander, Stampeding Kodo, Azure Drake), guys with great stats (Yeti), Value Creatures (Cult Master, Brewmasters).
d. Guys with good abilities but not necesarily good stats (Owl), vanillas with OK stats (3/2 for 2 Dino).
e. Least of 3 evils - when you get 3 sucky cards, one that sucks the least

Second thing to pay attention to is the curve. You want to curve out at 6 and 7, and you want your curve to top (have most cards at) 4. Sometimes 3 or 5, if you are playing a slower/faster deck.
---
As for actual play, few things are to be considered:
a. Maintain board advantage - most important thing. Whenever you can remove their creatures, if you make the trades they are profitable for you, if they make them, it is profitable for them. Any "weak" creature left can be Boosted with a Cleric or Dwarf and kill your much better guy. Of course, there are exceptions to the rule, but generally if you can, remove their creatures.
b. Maintain card advantage - trade 2 for 1. Save your removal for prime targets when possible, try to get at least 2-3 guys with your board wipe. Use your cards efficiently, if you have similar board position and he has more cards, he is generally in much better shape.
c. Know your opponent - VERY, very important. You need to know strengths of your opponent and play around them. For example, on 5 mana, Priest can cast Holy Nova. Never put two guys with 2 hp on turn 4, you are just giving him cards/board advantage. Similary, do not play out your big threat against Priest to get Mind Controlled - play them if you can remove them or after he used his Mind Control.
Can't list them all, in a rush, but they are mostly "X damage to everything" spells and some few others.
--
As for constructed, I started enjoying it A LOT.
I have a few decks, 3 are mostly complete:
Hunter's Unleash the Hounds - Its a Combo-Control thing, you control the board for 6-9 turns, than, you drop a lot of 1 mana beasts, cast Unleash the hounds and win in 1 swing.
Suicide Warlock - basically, lot of aggressively costed creatures with drawbacks that you basically try to ignore.
Hunter's Zoo - basically, play beasts and attack each turn.
And two that I needs a bit more cards for, but they are still nice:
A Mage and a Priest Control.
Also, I oppened Tirion Fordring recently, so am going to be making a Paladin.

Totally hooked on Hearthstone
