My memory was that it was always there - I never had the dvds as a kid but taped all the episodes when they aired, but have rewatched the dvd versions many more times by now - and it seems that others are saying the same.
IIRC, he was originally in the pilot, but the writers didn't have a story line planned out for him. They just knew they wanted to integrate him in some way, shape or form, so they went for it.