On "The Andy Griffith Show" (you know, Mayberry, Aunt Bea, Opie and Barney Fife), Andy Griffith would look at the scripts and say, "That sounds too much like a joke--let's cut that out." He wanted the humor of the situation to flow naturally out of the characters. I would say (IHNHO) that much of the muppet humor flows directly from the characters themselves--Kermit's the-only-sane-man (er, frog), Piggy's over-the-top diva, Gonzo's inexplicable but never boring weirdness, Rizzo's avarice.
I'm not saying that the characters had one dimension--but that the humor came not out of what Piggy did, or what Fozzie said, but from what we--as viewers--had come to expect from Kermit or some other character when they did.
They also did a lot of verbal humor--puns and that sort of thing. "Do you like Kipling?" "I don't know--I never Kippled!" And running gags--like Fozzie's telephone gags.
One of my all-time favorites in when Dr. Bunsen Honeydew dances with one of the whatnot muppets during the "At the Dance" segment. (Comments about formulaic humor coming up!) As they stop, he looks at here and say, "I see you have nothing to say." And later, "I see you STILL have nothing to say!" Not sophisticated AT ALL, but I fall out laughing every time.
Now, about formulaic humor... There's a lot to be said for the expected and familiar. Every time Vetrinarian's Hospital came on, we knew we were in for corny jokes, bad puns and lots of laughs at the expense of the hapless victims, er, patients. So, before the announcer even started his spiel, we were already shaking our heads in bemusement and ruefulness. If they were funny--hurrah! We laughed our, um, hind part's off. If they weren't funny--well, no surprises there!
If you're having trouble writing humor for a particular scene, try to visualize what the characters would do if you were watching them. (I realize that this would be easier if Jim or Frank or Steve or Bill were actually PUPPETING the muppets in your head, but we can't have everything, can we?) If you aren't a visual sort of writer, then start with a funny idea, a lame joke or a silly premise and see if you can work the characters in.
Hope some of this helped! I look forward to seeing what you come up with!