Nutshell:
— Play as many games as you can!
I think that the best approach to learning Go by playing is to play as many games as possible, mostly fast games, without thinking about your moves for too long (but still thinking!)
This is not to say you should play thoughtlessly, just that spending too much on each move is less productive at this stage than playing a larger amount of games. You will probably know when it is time to think more and which moves are worth the extra effort as time goes by and you gaing more experience. For now, do not worry about that too much, or you might bore your opponent (and yourself).
I would suggest games no slower than 15/15, which means 15 min main time with 15 min extra time (called byo-yomi) for each additional 25 moves. Or something like that.
Go is in large part a pattern-recognition game, so the goal is to gain as large a database of patters as possible in the shortest amount of time. Playing a large number of games is probably the most natural and enjoyable way of accomplishing that.
However, you must also take into account your own style and temperament. I have met beginners out there who honestly enjoy the game more when playing slower, sometimes even as slow as 60/60! To each his or her own, and this is ok so. Just take into account that you will probably have some more trouble finding opponents to play such slow games at your level, especially on the web.
On the other hand, I would not advise to play games which are too fast. This woudl defeat the purpose. Go is, after all, a game in which you are supposed to think. Right? So, I would suggest you play no faster than 5/5 if you want to get any real benefit from the game. Below that, games become a stone-dropping or a mouse-clicking contest.
The reason for that is that larger boards may be too complex, and the games are too long to finish on them. There are too many moves to make, too many possible places to play, and too many ideas to explore at once. A time will come to graduate from the 9x9 board, but for now, just give it a try.
About 100 games on 9x9 is ok, I'd say, but it varies from player to player.
After that, try playing about the same number of games on 13x13, although it might take more than this. The 19x19 board is not easy.
Above all, do not play on larger boards if it is no fun for you. This is important. I have seen quite a few players getting dicouraged and dropping the game altogether because they tried to force the issue and started playing on a too large board too soon.
On the other hand, I never played on boards smaller than 19x19 when I was learning the game, and for me it was just fine. But I have to admit that it is not the usual case. 19x19 boards can be boring for beginners. I was simply lucky to have had a great teacher.
This usually imply strong(er) players. With or without handicap, games against stronger players are probably your main source of Go education. Especially if they are gracious enough to provide you with some hints after or during the game. Or maybe even a full game analysis. Such things are priceless to a newbie!
Therefore, treat strong(er) player with respect. But not with awe! Just remember - they are stronger only because they have spent more time playing and studying the game than you have. For now...
Sometimes players of your own level, or even weaker, can be challenging. When their "style" is especially uncomfortable to you, or they are unusually tenacious and stubborn in clinging to groups you want to kill... even if you manage to always win against such players, the games might be educational to you.
Just because you can beat them, does not mean that there is nothing you can learn from them!
So treat weaker players with respect too! Always think that a time might come when the student will become a master, and you might regret time you spent taunting weaker players when they finally surpass you. And they might, they might. And probably will... :)
Come to think of that, best to just treat everybody with respect!