Стайнберг изучал социологию и психологию в Бухарестском университете (с 1932 г.), получил степень доктора архитектуры в миланском Политехническом институте (1940). В 1940-41 гг. работал архитектором в Италии.

Его первые карикатуры были опубликованы в миланском журнале "Бертольдо" в 1936 г. В 1941 г. Стайнберг начал сотрудничать с журналом "Нью-Йоркер", а через год из-за антисемитизма, усилившегося в это время в Италии, переехал в США, обосновавшись в Нью- Йорке. Художник участвовал во Второй мировой войне, служил в американском флоте (1943-45) - рисовал антинацистские карикатуры, которые потом разбрасывали над территорией, занятой врагом. В 1946 г. он был специальным корреспондентом "Нью-Йоркера" на Нюрнбергском трибунале.

Первая персональная выставка Стайнберга состоялась в Нью-Йорке в 1943 г. В 1945 г. он опубликовал первый свой альбом "Всё в линию". Среди других его альбомов – "Искусство жить" (1949), "Лабиринт" (1959), "Каталог" (1962), "Новый Свет" (1965), "Маска" (1966). Его многолетняя работа в "Нью-Йоркере" оказалось необычайно плодотворной: журнал напечатал 642 его рисунка, включая 85 обложек. Он много путешествовал, в 1956 г. посетил СССР, создав цикл иронических рисунков о разных республиках.

Уже в начале 1950-х годов Стайнберг вышел за рамки журнальной публицистики, экспонируя свои вещи в авангардных музеях и галереях, таких как нью-йоркский Музей современного искусства, парижская галерея Мэг и др. Он достиг особой, прихотливой свободы линии, – она у него как бы сама начинает творить росчерки и виньетки, из которых складываются фигуры и пейзажи, составившие со временем пародийно-юмористическую панораму американского "общества потребления". Монументальным вариантом этой панорамы стало настенное панно Стайнберга, украсившее павильон США на Всемирной выставке в Брюсселе (1958). Позже, используя технику коллажа, а также трёхмерных инсталляций, Стайнберг придал карикатуре статус авангардистского искусства, оказав воздействие на зарождение поп-арта.

Имя Сол - английская форма библейского имени Саул. Фамилия Штейнберг произошла, вероятно, от названия города Штайнберг в Саксонии, Германия.