Yea he has changed over the years... probably as a result of different artists interpretations of him. Each artist gives a different interpretation of Graham, which is influenced by technological limitations as well as growing vision. The Graham in KQ1 is a new character with little known about him... whereas in KQ5, there's a great deal known about him, both in terms of story and design. It's evolution in practice.
Directly from Mobygames:
King's Quest: Quest for the Crown (1984)
Graphics by Doug MacNeill, Greg Rowland
King's Quest II: Romancing the Throne (1985)
Graphics by Doug MacNeill, Mark Crowe
King's Quest III: To Heir is Human (1986)
Graphics Doug MacNeill, Mark Crowe
King'a Quest IV: The Perils of Rosella (1988)
Graphics / Artwork William D. Skirvin
King's Quest V: Absence Makes the Heart Go Yonder (1990)
Deena Benz, Ernie Chan, Jeff Crowe, Richard D. Zeigler-Martin, Tamra Dayton, Dana M. Dean, Roger Hardy, Douglas Herring, Eric Kasner, James Larsen, Cheryl Loyd, Hector Martinez, Harry McLaughlin, Gerald Moore, Maurice Morgan, Vasken N. Sayre, Jennifer Shontz, William D. Skirvin, Cheryl Sweeney, Barry T. Smith, Cindy Walker, Deanna Yhalkee
King's Quest VI: Heir Today, Gone Tomorrow (1992)
Art Designer William D. Skirvin
Senior Artist Michael Hutchison, John Shroades
Team Artist Russell Truelove, Deanna Yhalkee
Darlou Gams, Tim Loucks, Richard Morgan, Jennifer Shontz, Cindy Walker, Karin Ann Young
King's Quest: Mask of Eternity (1998)
Graphics / 3D Programming
Ray Bornstein, Robert Munsil, John Piel, Barry Sundt, William Todd Bryan, Marc Vulcano, Ethan Walker, Jason Zayas
You'll notice that in the beginning, there were only two artists for the first couple of games... who did every sprite and every background. However, with KQ5, the team got expanded quite a bit. This also plays a part in complexity of character design, as you can break the workload up between multiple artists so as to increase quality of each art asset created instead of having two artists creating every art asset in a game within a certain time-frame.
You'll also notice that Doug Macneill, who was an artist on the first 3 KQ games, disappeared from the credits after KQ3, being replaced by William D. Skirvin. This change represents a major shift in art design and explains why Graham's appearance changes. William D. Skirvin is the one responsible for Graham's KQ5 appearance, which is basically just a more detailed (read: more colors and bigger sprite) version of what he looked like in KQ4. And since he was the one who did all the art for KQ4... well you get the picture.