I currently own an iPhone 3G and tether using PDAnet.

If I upgraded to a 3GS iPhone, would the speed of the internet on the laptop be faster?

I went into the apple store and loaded the same sites on my #G iphone and on ehtier 3GS. The 3GS was slightly faster. The salesman said that this is because the 3GS has a faster processor. Would the faster processor increase the speed while tethering? Anyone know?

I would say probably not. As far as I know, tethering is not a processor speed critical activity like web page rendering is. You may see a small speed increase, it's difficult to know for sure without actually testing it.