I recently worked on a project which involved deriving the medial axis (distinct from centerline, but similar) of stream features by using stream bank polyline features extracted from high-res imagery. It was important for us to make the distinction for our purposes, as the medial axis was to be used for orthogonal generation, and thus needed to be a generalized center of our stream features and not the exact middle of the stream.
The method we ended up using was a python script which took in our two polyline features, added verteces at a given interval (~5m), and then looped through each vertex in one polyline, and searched for the nearest vertex in the other polyline. There were some specific situations that were handled differently (extreme bends in the stream that would find a vertex closer than the true corresponding one on the opposite bank), but I didn't write the code so I would have to get a hold of it to understand what was really going on.
Before we decided on our method, the guy working on the scripting toyed with some alternatives and used Euclidean Allocation using the bank polylines as input, and then created a contour from the resulting raster. It was a brilliant way to get the centerline, but not what we were looking for. This might work for you, though.
You should spend some time thinking through what you will be using the centerline for, and if you should be looking for a centerline or generalized medial axis.