Not sure what others would do, I would first learn a language (such as C). For cross-platform languages, you can probably do a lot without anything Linux specific. I would also take a look at the Linux system calls (there's a list at
linux.die.net).
I've never read the book (I can't remember reading a Linux specific programming book), but I've gotten pretty far anyway. I started my programming by reading an online copy of
The C Book. I think it has exercises, too. Just get a copy of some text editor (one with syntax highlighting helps) and make sure your distro has a C compiler and go with it!