Some years ago, when I bought my first custom knife, I used it to cut a slice of ham. The blade was "stained" immediatly.
I went back to the knifemaker's shop where I had bought it ... not sure if it was a defect or not ....
But that's carbon steel to you, as other posters have explained..
and yes, after some use, it gives a nice patina.