Shakey's Pizza is based on a real restaurant franchise[1] and was first seen in the Season Five episode "Kenny Dies".
Background
In "Kenny Dies", Eric Cartman's love for the restaurant inspires him to make another for himself using the stem cells. This plot of his was later referenced in "The Death of Eric Cartman".
In "Stanley's Cup", Stan Marsh mentions visiting the restaurant after a big hockey game.