I recently watched Star Trek season 1 episode 22, Space Seed, which is the first appearance of Khan Noonien Singh.
I didn't see Chekov anywhere in that episode, and I was waiting for him to show up and have some interaction with Khan. You can see from the clip of Wrath of Khan below that Khan and Chekov clearly recognize each other immediately when they meet on Ceti Alpha VI:
I did some Googling and found out Chekov joined the crew just in time for the events of Space Seed, so he was definitely on the ship somewhere:
Chekov's first assignment, at the age of 22, was on the USS Enterprise under command of Captain James T. Kirk. He joined the crew sometime prior to the spring of 2267. (TOS: "Catspaw", "Who Mourns for Adonais?", "Space Seed", "I, Mudd"; Star Trek II: The Wrath of Khan)
Is it ever explained anywhere how they recognize each other?
Did they just meet off camera somewhere or in some deleted scene perhaps?