Летали. Потеря способности летать у пингвинов - это эволюционный феномен, выраженный в общей дегенерации.
С другой же стороны, пингвины увеличились в размерах, их крылья стали более жесткими, их мышцы также увеличились - данная идиоадаптационная составляющая эволюционного процесса в комбинации с общей дегенерацией позволила им чувствовать в воде себя комфортнее.
В общем, благодаря потери способности к полету пингвины смогли занять свою уникальную экологическую нишу.