I think that software is the first concern here.... the quality of your results depends more on the software than the camera and lens being used. My choice is AutoPano Giga... if you end up with big panos it's a wonderful tool!
I have shot handheld panoramas and tripod mounted panoramas..... both work, but if you are going to use anything other than really wide angle lens I recommend the tripod. Take your time setting up the tripod... time spent here is never wasted. You want it to be as level as possible, and a head with degree markings comes in real handy for taking panoramas with multiple rows... also, beware blue sky.... it is very hard to stitch together pictures with blue sky... there is nothing to match between frames.
If doing multiple rows, it helps to proceed in a systematic order.... for example, top ring, next ring, next ring, and so on... Try to make sure you start at the same degree marking so the pictures line up. (hint, I take an index shot of my hand with one finger out at the start of row one, two fingers at the start of row 2, etc.... makes it easier looking at the frames later)
The more images per picture, the less distortion you get. The attached pano is 4 rows and 24 shots per row.... the full image is about 1Gpixels in size and you can clearly see that the screws used on the gunnels of the canoe have a robertson head