The first official "graduation" is in the third book of the Jedi Academy trilogy, but anytime Luke encounters a Force sensitive he seems to have an inability at not teaching them what he has learned. The first property that has Luke "showing off" his skills to a potential student is somewhere in the Marvel series I think, but he isn't willing at that time to formally take on any students.
11 ABY - "Champions of the Force" (part 3 of KJA's Jedi Academy Trilogy). Some of those events also retold in MAS's "I Jedi".
I only vaguely remember the end of the JAT, but I more distinctly remember Dorsk 81 and Kyp Durron being his first official wandering Jedi Knights in Darksaber. In JAT, Luke's first Jedi class defeated Exar Kun, so that's definitely an impressive achievement, but I think Dorsk and Kyp are the first who are told to go out and help the galaxy. Although it was kind of funny having Kyp be one of the first graduates, but oh well. My memory is probably still off too. I think there was this short story in one of the anthologies where Kyp was traveling around under an assumed name, because of the shame he felt over his actions (far different from the brash, aggressive Kyp we got when the NJO started).
Well, according to Darksaber, the first three Jedi Knights to be fully graduated are Kyp Durron, Dorsk 81, and Cilghal. Not that KJA was consistent with any of this. --Adm. Nick
As others have said, the first Jedi to be fully Knighted were Kyp Durron, Cilghal, and Dorsk 81, in Darksaber.