They are definitely different, but soft body simulation is very slow compared to cloth.. why?
In short, soft bodies are compressible while cloth is not. All other features are the same.
However, this makes a huge difference in computational speed. To better explain this, I will use an extension of the metaphor CharlesL used in his response.
A Cloth Simulation essentially models the object as a bunch of balls (vertices) connected to each other by fixed-length rods. Thus, for computational purposes, the simulation can treat the internal distances between points as a constant, and only has to calculate interaction with other objects.
A Soft Body Simulation, on the other hand, models the object as a bunch of balls (vertices) connected to each other by springs. So now, not only does Blender have to compute the interaction of the object with other objects, but also has to compute its own internal reaction and the spread of force applied at one point across all of those little springs, which is much more complex.
I don't know the exact complexity of the algorithms Blender uses for these simulations, but it's essentially the difference between a linear relationship and a differential equation.
5$\begingroup$ According to Todd Koeckeritz (Blender Cloth Developer), the Cloth Simulation uses a Spring Network (not fixed-length rods). More information can be found here: blender.stackexchange.com/questions/8247/… $\endgroup$ Apr 22, 2015 at 18:20
2$\begingroup$ Also, the "Structural" and "Bending" parameters in the Blender Cloth Panel represent the Spring Network's stiffness, as seen in the Blender Cloth Manual: blender.org/manual/physics/cloth.html $\endgroup$ Apr 22, 2015 at 18:30
2$\begingroup$ Additionally, Blender uses Provot's Cloth Model. In Provot's model "all springs have a natural length non equal to zero but they remain nevertheless intrinsically linear springs." $\endgroup$ Apr 23, 2015 at 18:13
1$\begingroup$ However, Kass/Pixar did come up with "fixed-length" springs similar to Provot's structural springs. Kass reads: "With only fixed-length springs along the mesh edges, the simulated clothing can undergo arbitrary skew without penalty. One way to prevent the skew is to introduce fixed-length springs along the diagonals. The problem with this approach is that strong diagonal springs make the mesh too stiff, and weak diagonal springs allow the mesh to skew excessively." $\endgroup$ Apr 23, 2015 at 18:18
1$\begingroup$ More completely, the Provot model states: "everything happens as if the springs were classical springs up to a certain deformation rate and quasi rigid rods above this deformation rate" $\endgroup$ Apr 23, 2015 at 18:24
I'm not sure about speed and optimization but there are some differences between the two. Here is what the documentation says about the softbody simulator:
A Soft Body in general, is a simulation of a soft or rigid deformable object. In Blender, this system is best for simple cloth objects and closed meshes. There is dedicated Cloth Simulation physics that use a different solver, and is better for cloth.
This simulation is done by applying forces to the vertices or controlpoints of the object. There are exterior forces like gravity or forcefields and interior forces that hold the vertices together. This way you can simulate the shapes that an object would take on in reality if it had volume, was filled with something, and was acted on by real forces.
So basically the soft body measures where each vertex should be pushing the vertices around it. Kind of like a bunch of opposing magnets connected by string.
The cloth simulator works more along the lines of each vertex having mass and simply falling and folding without much care as to the other vertices around it (except of course for collisions). It's more like a bunch of marbles connected by string.
Soft bodies are generally better for enclosed meshes (i.e. no non-manifold edges) and things that will bounce or jiggle or conform to its surroundings.
Cloth is better for non-manifold meshes that will fall and collide with other meshes. It works better with things like clothing, flags or bed sheets.