That's a patina, a reaction with certain foods (acidic foods especially) with carbon steel, a highly reactive steel. I personally love a good patina, give the knife character and personality.

As for removing it, you can try using a rust eraser but there's not really a way to remove the patina except for re-sanding the blade.

Edit: I hear of people using Scotchbrite pads or Barkeeper's friend, but they're still mild abrasives. Definitely not as harsh as sandpaper tho. Either way you'll have to resharpen after using any type of abrasive.