I have just recently started to play go and am going to track my progress here. I'm currently 19k on kgs due to playing robots, but likely closer to 25k in reality.
The most important advice I see when starting out is to play a lot and get comfortable with the game. To do this I am playing Goban on 9x9 games until I can beat it at the hardest setting. So far I'm about 50% at the easiest setting.
I've also started to study the Korean academy life and death problems at gobase.org.
Making a base
I've been spending most of my time on the Korean academy problems and Graded go for beginners (Volume 1). In the 9x9 games I am getting much better results by paying more attention to the health of my own stones rather than always trying to push the opponent around.
18 kyu on kgs
I've been going through some of the lessons at GuoJuansInternetGoSchool and they are definitely helping. I played a game tonight on KGS and was much more willing to give up stones to make more territory and capitalize on my opponents mistakes. I only have a few games so the variance is high, but I moved up to 18 kyu after the game.
15 kyu on kgs
So far I'm improving rather steadily, but in recent games it is more due to opponents mistakes than solid play on my part. The GuoJuansInternetGoSchool lessons are still my primary form of study, but I'm having trouble focusing on them seriously. The format makes it very easy to watch lessons passively like TV shows. My short term goal is to go through three of the audio lessons and spend more time working through each of the exercises.
For go problems, I've started to read GradedGoProblemsForBeginners Volume 2 and it is still a challenge. I can comfortably go through all of the Volume 1 problems in a single sitting and I've stopped reviewing the first two sections of Volume 1 all together.