My rough journey so far - on a Mac, but much of this can be done on Linux - I started out playing 9x9 games against Gnugo, giving myself as much handicap as possible (without it resigning immediately), and then removing stones as I improve. I got to the point where I could sometimes beat 9x9 when I started with two extra stones, and then I started with 19x19.
Took me a while to win 19x19 with 9 stones, but then I won by learning a bit more about extending on hane. Then you can improve from there.
After that point, you can also switch to fuego or pachi, which are stronger by default. The end result is it really is easy and possible to learn a ton just by playing against software, tracking your ability throughout, just by picking programs with different strength and handicap levels.
I've also enjoyed using GoGui to pit two computer programs against each other and watch how they play with various handicaps.
Then there's all the puzzles - goproblems.com, smartgo, etc. Finally, there are plenty of ebooks you can buy through smartgo books.
This doesn't get into playing against humans on the various servers, but there's plenty of information about that online.