Apple 1 ads first appeared in the October 1976 issue of Interface Age magazine.
(Hmmm... or did the ad first appear as text only, in the September 76 issue?)
"Apple Introduces the First Low Cost Microcomputer System with a Video Terminal and 8K Bytes of RAM on a Single PC Card"
UPDATE FEB.10.2010: It turns out that the September 1976 issue of Interface Age is where the first Ad for the Apple-1 appeared, not the October issue. I will have images on the way soon. Stay tuned!