You could laminate them with a tile effect design, as above, or use parquet to give it a nice finish although that'd be more expensive and since the bannister is painted also that might well be the way to go. Cheaper too.
If you wanted to remove all the paint you could try a heat gun to carefully scrape and sand away the old layers but that'd be time-consuming and messy, so it all comes down to the kind of finish you want, bearing in mind wooden stairs are noisy to use in a terraced (?) house.