Well, The Jim Henson Company helped the fans know the names by having them included in that coloring book!
Actually, for a long time I kind of did wonder. Over the years I thought it strange and pointless that characters would get proper names (as opposed to their official names being descriptive like "Comic Book Guy") without being mentioned on-screen, but then realised they may have planned to eventually mention the names but it never came up. And realised that just because a writer/producer wanted a character to have a name in a movie doesn't mean they thought before writing the script how the names would be mentioned ("okay, we'll call this guy Ted. He's only in a few scenes and not really important to the plot, but we've got to make sure he's mentioned by name somewhere").
On the Muppet Wiki talk page I asked about where Gaffer's name had been mentioned and I was told it's mentioned in a caption in The Art of the Muppets (a few issues of The Muppet Show Fan Club Newsletter refers to it as "Theater Cat").
I haven't read Of Muppets and Men but based on somethings I've read I'm assuming Lips is referred to by name there. Lips is listed in the credits under Steve Whitmire's characters in The Great Muppet Caper (does the same apply to the soundtrack credits?). I remember when I first noticed his name in the credits, it was after I'd known the names of all the other credited Muppets, so figured it must have been him, but also figured it best not to assume until I saw a real confirmation. But it is a little odd, and quite a few other characters aren't mentioned by name at all in the movie (Dr. Teeth, Floyd, Janice, Zoot, Bunsen, and I don't think Scooter is called by name). I know they didn't need to introduce everyone by name again (since so many of them were "introduced" in The Muppet Movie), but still...
And while we're on the subject of The Great Muppet Caper, I think that Lips should have responded to Fozzie checking off "wax lips". Though for whatever reason Lips wasn't in that scene at all.
Steve Whitmire talked about performing Lips in his interview at Muppet Central, which definately confirms the character's name. And both Lips and Gaffer were made as action figures (Gaffer an accessory for Pops), with their names written on the label. All that should be enough proof of their names.
By the way, I don't think I'd ever heard about that Meet the Muppets coloring book before. Sounds cool. What other characters appear?