According to Hearthstonecast from July 2013
"Matches in “The Arena” mode follow a match making protocol to ensure that players of similar play strength (meaning players with comparable win/loss records) are matched up against each other. Obviously, such a system would improve over time and not be as reliable in the early stages of Hearthstone going live."
Current (unconfirmed, fan-based) thinking is each match you are matched to someone with the same Arena score as you, so for your first game you are playing someone who is also on 0-0, if you then lose, your next game will be against someone who has also just lost one game.
I would guess as well that matchmaking is something that will be being fine-tuned for a while.