How did this stone become encased within different rock?
it was simply an older stone smoothed by water that had fallen into sediment.

This is exactly what happened. There's a name for that: a conglomerate.