I have one lens hood for a 28-105mm lens that is petal shaped. I have another lens hood for a 50mm lens that is fully round. If the purpose of the lens hood is to block stray light, then wouldn't fully round always block more?
As Chills stated, petal shaped hoods are designed to better take into account the wider shape of a camera's film or sensor.
This article on Lens Flare has a good description of lens hoods and how they function.
The petal design is more effective. Think of what you can see through your lens: it is a pyramid-shaped chunk of space that falls within your view, one that has a rectangular rather than a square base. Now imagine placing a round lens hood atop that pyramid - there will be a large gap on each side, because the corners bump into the round opening first. A petal-shaped hood fills in these gaps, excluding more stray light.
Every lens projects a circular image, but film and digital sensors are rectangular. In the case of DSLRs, the rectangle is usually quite oblong, with the standard 3:2 aspect ratio — that is, half again as much width as height.
The more a lens hood shades except the part that forms the image, the better. Petal hoods can take advantage of this by providing more shading for the parts of the frame that are farthest from the edge of the circle (primarily the top and bottom, followed by the edges) and less shading where the frame gets close (the corners).
Focal length is also a big factor, again for logical reasons — the wider the lens, the wider the hood has to be to stay out of the way. This means that for longer focal lengths ("telephoto lenses"), a tubular non-petal design can provide quite a lot of shade, and going to a petal design is basically unnecessary and could be even unwieldy, protruding way, way out.
As a practical example, the following image was taken with a 23mm lens, which has a nice petal hood, but which I had quickly attached so that it was diagonally-askew rather than on straight. You can see exactly what it'd be like if the hood extended to the length of the petal all the way around:
Short answer: Yes, a round tubular lens hood will always block more stray light than a petal-shaped lens hood.
BUT, that's only half of the answer, however. The part that is missing is, "without cutting off (vignetting) the corners of the image at the widest angle used, in the case of a zoom." (an important omission, no?)
The petal shape is one compromise solution unless designed specifically for a particular fixed-focal lens.
Another solution is used by some manufacturers who make an over-size tube lens filter and then cut a rectangular window in the end for the light blocking.
Motion picture cameras have such a thing attached to the camera mount in some way. It is also called a matte box and allows various inserts to mask the shot from various things and for various effects. It is a pleated accordion-fold affair that allows it to be changed for various set-ups.