Etymonline says surfing in the Internet sense was first recorded 1993. Now that's precise. The author of the 1992 article Surfing the Internet has made a little research herself and found Brendan Kehoe mention the term in 1991 to describe people who try out guest accounts on Internet hosts, which isn't exactly what we mean. But she also found out that Mark McCahill, creator of gopher, the short-lived predecessor of the WWW, had used the phrase "surfing the internet" in 1992 to describe how easily you can move from server to server using gopher hyperlinks.
I remember surfing the web being an insult of superficiality around 1992/1993, but only found this statement to support this theory. Many netheads were annoyed by the new crowds of people surfing the WWW. Until the web came, file transfers were only done when truly necessary. You would not look at a picture just because it is there — you would make a conscious decision to download it. Using a web browser was too easy, you would walk around colourful pages, clicking on hyperlinks. Websurfers was an insult directed at those people who would click on a link, have a web page loaded with lots of graphics, only to decide they didn't like it and quickly surf away again. These folks were suddenly causing a load the Internet had never seen before. Soon after the first release of NCSA Mosaic the amount of traffic generated by HTTP would dwarven the FTP traffic, that had been the number one load on the net until then. Our university was particularely hit by the advent of the web as all of its students and personnel were connected to the rest of the Internet over a crappy 64K X.25 line. See also the related German insult Klickibunti.