According to the philosophical system of Aristotle and his followers, there are four causes or reasons that describe a thing; these causes can be analyzed to get to a solution to the paradox. The formal cause or form is the design of a thing, while the material cause is the matter that the thing is made of. The "what-it-is" of a thing, according to Aristotle, is its formal cause; so the Ship of Theseus is the same ship, because the formal cause, or design, does not change, even though the matter used to construct it may vary with time. In the same manner, for Heraclitus's paradox, a river has the same formal cause, although the material cause (the particular water in it) changes with time, and likewise for the person who steps in the river.
Another of Aristotle's causes is the end or final cause, which is the intended purpose of a thing. The Ship of Theseus would have the same end, that is, transporting Theseus, even though its material cause would change with time. The efficient cause is how and by whom a thing is made, for example, how artisans fabricate and assemble something; in the case of the Ship of Theseus, the workers who built the ship in the first place could have used the same tools and techniques to replace the planks in the ship.
This probably won't do as a solution to the problem, though, since the material cause does change over time, and we have been shown no reason to privilege one of the causes over another in the determination of continuity of identity.
Definitions of "the same"
One common argument found in the philosophical literature is that in the case of Heraclitus's river we are tripped up by two different definitions of "the same". In one sense things can be qualitatively the same, by having the same properties. In another sense they might be numerically the same by being "one". As an example, consider two bowling balls that look identical. They would be qualitatively, but not numerically, the same. If one of the balls was then painted a different color, it would be numerically, but not qualitatively, the same as its previous self.
By this argument, Heraclitus's river is qualitatively, but not numerically, different by the time one attempts to make the second step into it. For Theseus's ship, the same is true.
The main problem with this proposed solution to problems of identity is that if we construe our definition of properties broadly enough, qualitative identity collapses into numerical identity. For example, if one of the qualities of a bowling ball is its spatial or temporal location, then no two bowling balls that exist in different places or points in time could ever be qualitatively identical.
Likewise, in the case of a river, since it has different properties at every point in time—such as variance in the peaks and troughs of the waves in particular spatial locations, changes in the amount of water in the river caused by evaporation—it can never be qualitatively identical at different points in time. Since nothing can be qualitatively different without also being numerically different, the river must be numerically different at different points in time.
One solution to this paradox may come from the concept of four-dimensionalism. David Lewis and others have proposed that these problems can be solved by considering all things as 4-dimensional objects. An object is a spatially extended three-dimensional thing that also extends across the 4th dimension of time. This 4-dimensional object is made up of 3-dimensional time-slices. These are spatially extended things that exist only at individual points in time. An object is made up of a series of causally related time-slices. All time-slices are numerically identical to themselves. And the whole aggregate of time-slices, namely the 4-dimensional object, is also numerically identical with itself. But the individual time-slices can have qualities that differ from each other.
The problem with the river is solved by saying that at each point in time, the river has different properties. Thus the various 3-dimensional time-slices of the river have different properties from each other. But the entire aggregate of river time-slices, namely the whole river as it exists across time, is identical with itself. So you can never step into the same river time-slice twice, but you can step into the same (4-dimensional) river twice.
A seeming difficulty with this is that in special relativity there is not a unique "correct" way to make these slices -- it is not meaningful to speak of a "point in time" extended in space. However, this does not prove to be a problem: any way of slicing will do (including no 'slicing' at all), provided that the boundary of the object changes in a fashion which can be agreed upon by observers in all reference frames. Special relativity still ensures that "you can never step into the same river time-slice twice", because even with the ability to shift around which way spacetime is sliced, you are still moving in a timelike fashion, which will not multiply intersect a time-slice, which is spacelike.
Metaphysics of quality
Robert M. Pirsig's metaphysics of quality, presented in Lila: An Inquiry into Morals, defines a hierarchy of patterns and uses it to offer another solution to the paradox: the ship is simultaneously a set of lower-order patterns (the parts) which change, and a single higher-order pattern (the ship as a whole) which remains constant.
This concept may differ among different cultures. As an anedocal evidence it seems that in the east this is not a paradox. Quoting Douglas Adams from the book Last Chance to See:
I remembered once, in Japan, having been to see the Gold Pavilion Temple in Kyoto and being mildly surprised at quite how well it had weathered the passage of time since it was first built in the fourteenth century. I was told it hadn't weathered well at all, and had in fact been burnt to the ground twice in this century.
"So it isn't the original building?" I had asked my Japanese guide.
"But yes, of course it is," he insisted, rather surprised at my question.
"But it's burnt down?"
"Of course. It is an important and historic building."
"With completely new materials."
"But of course. It was burnt down."
"So how can it be the same building?"
"It is always the same building."
I had to admit to myself that this was in fact a perfectly rational point of view, it merely started from an unexpected premise. The idea of the building, the intention of it, its design, are all immutable and are the essence of the building. The intention of the original builders is what survives. The wood of which the design is constructed decays and is replaced when necessary. To be overly concerned with the original materials, which are merely sentimental souvenirs of the past, is to fail to see the living building itself.