Ray marching is an iterative ray intersection test in which you step along a ray and test for intersections, normally used to find intersections with solid geometry, where inside/outside tests are fast.
Images from Rendering Geometry with Relief Textures
A fixed step size is pretty common if you really have no idea where an intersection may occur, but sometimes root finding methods such as a binary or secant search are used instead. Often a fixed step size is used to find the first intersection, followed by a binary search. I first came across ray marching in per-pixel displacement mapping techniques. Relief Mapping of Non-Height-Field Surface Details is a good read!
It's commonly used with space leaping, an acceleration technique where some preprocessing gives a safety distance that you can move along the ray without intersecting geometry, or better yet, without intersecting and then leaving geometry so that you miss it. For example, cone step mapping, and relaxed cone step mapping.
Sphere tracing may refer to an implicit ray-sphere intersection test, but it's also the name of a space leaping technique by John Hart, as @joojaa mentions, and used by William Donnelly (Per-Pixel Displacement Mapping with Distance Functions), where a 3D texture encodes spheres radii in which no geometry exists.
They belong to the same family of solvers, where sphere tracing is one method of ray marching, which is the family name.
Raymarching is a technique a bit like traditional raytracing where the surface function is not easy to solve (or impossible without numeric iterative methods). In raytracing you just look up the ray intersection, whereas in ray marching you march forward (or back and forth) until you find the intersection, have enough samples or whatever it is your trying to solve. Try to think of it like a newton-raphson method for surface finding, or summing for integrating a varying function.
This can be useful if you:
Image 1: Traditional ray marching for surface finding
Sphere tracing is one possible Ray marching algorithm. Not all raymarching uses benefit form this method, as they can not be converted into this kind of scheme.
Sphere tracing is used for rendering implicit surfaces. Implicit surfaces are formed at some level of a continuous function. In essence solving the equation
F(X,Y,Z) = 0
Because of how this function can be solved at each point, one can go ahead and estimate the biggest possible sphere that can fit the current march step (or if not exactly reasonably safely). You then know that next march distance is at least this big. This way you can have adaptive ray marching steps speeding up the process.
Image 2: Sphere tracing* in action note how the step size is adaptive
For more info see:
* Perhaps in 2d it's should be called circle tracing :)