I don't think I learned much from specific CGI-oriented tutorials or books, which, looking back, kinda surprises me.

I tend to be a "top down" kind of learner though, moving from theory to practice, so I got myself a bit of a basis in Perl first and then extended it to the CGI arena. I went with the Llama book (which is for some reason available under the title "Learning Perl" =) for both (I think the chapter on CGI in there is pretty good, actually) and an Apache book, now I can figure things out from my still limited theoretical knowledge.